Сложные высказывания можно записывать в виде формул. Для этого простые логические высказывания нужно обозначить как логические переменные буквами и связать. - презентация

1

2 Сложные высказывания можно записывать в виде формул. Для этого простые логические высказывания нужно обозначить как логические переменные буквами и связать их с помощью знаков логических операций. Такие формулы называются логическими формулами или логическими выражениями. Например: Чтобы определить значение логического выражения необходимо подставить значения логических переменных в выражение и выполнить логические операции. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке: 1. инверсия; 2. конъюнкция; 3. дизъюнкция; 4. импликация 5.эквивалентность. Для изменения указанного порядка выполнения логических операций используются круглые скобки.

3 Для каждого составного высказывания (логического выражения) можно построить таблицу истинности, которая определяет истинность или ложность логического выражения при всех возможных комбинациях исходных значений простых высказываний (логических переменных). При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий: 1) записать выражение и определить порядок выполнения операций 2) определить количество строк в таблице истинности. Оно равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение (определяется по формуле Q=2 n, где n - количество входных переменных) 3) определить количество столбцов в таблице истинности (= количество логических переменных + количество логических операций) 4) построить таблицу истинности, обозначить столбцы (имена переменных и обозначения логических операций в порядке их выполнения) и внести в таблицу возможные наборы значений исходных логических переменных. 5) заполнить таблицу истинности, выполняя базовые логические операции в необходимой последовательности и в соответствии с их таблицами истинности Теперь мы можем определить значение логической функции для любого набора значений логических переменных. Логической функцией называется зависимость значения одной переменной логической величины от значения других независимых логических величин – аргументов. Способ вычисления логической функции описывается логической формулой. Например: F(A,B,C)=(A&B) (Ā&C)

4 Например, построим таблицу истинности для логической функции: Количество входных переменных в заданном выражении равно трем (A,B,C). Значит, количество входных наборов, а значит и строк Q=2 3 =8. Количество столбцов равно 6 (3 переменные + 3 операции). Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C, промежуточных результатов и (B V C), а также искомого окончательного значения сложного арифметического выражения

5 ABCB V C

6 ABC

7 ABC Задание. Постройте таблицу истинности для данного логического выражения:

8 АВ Равносильные логические выражения. Логические выражения, у которых последние столбцы таблиц истинности совпадают, называются равносильными. Для обозначения равносильных логических выражений используется знак =. Например:

9 ABCне Вне Сиилии Заполнение таблицы: 1.разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»; 2.разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»; 3.продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа. Пример. Для формулы A&(B V не В & не С) построить таблицу истинности. Количество логических переменных 3, следовательно, количество строк = 8. Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов = 8.

10 Правила построения логического выражения: 1.Для каждой строки таблицы истинности с единичным значением функции построить минтерм. Минтермом называется произведение, в котором каждая переменная встречается только один раз либо с отрицанием, либо без него. Переменные, имеющие нулевые значения в строке, входят в минтерм с отрицанием, а переменные со значением 1 без отрицания. 2. Объединить все минтермы операцией дизъюнкция (логическое сложение), что даст стандартную сумму произведений для заданной таблицы истинности.

11 Пример. Дана таблица истинности: X1X2X3F Для второй строки X1=0, Х2=0, X3=1. Эту строку описывает минтерм Для третьей строки X1=0, Х2=1, X3=0. Эту строку описывает минтерм Для шестой строки X1=1, X2=0, X3=1. Эту строку описывает минтерм Объединяя термы, получим булевое выражение F = В это выражение вошли термы-произведения для строк с единичным значением функции F, а вся сумма соответствует совокупности из трех строк. Для остальных пяти наборов значений входных переменных это выражение равно нулю. Построим логическое выражение для F. Найдем строки, в которых F=1. Это вторая, третья и шестая.

12 Логические основы компьютеров К. Поляков, ABCX

13 Логические основы компьютеров К. Поляков, ABCX

14 Любое логическое выражение (составное высказывание) можно рассматривать как логическую функцию F(X1,X2,..., Xn) аргументами которой являются логические переменные X1, X2,..., Хn (простые высказывания). Сама функция как и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0). Выше были рассмотрены функции двух аргументов: логическое умножение F(A,B) = A&B, логическое сложение F(A,B) = AVB, а также логическое отрицание F(A) = ¬А, в котором значение второго аргумента можно считать равным нулю. Каждая логическая функция двух аргументов имеет четыре возможных набора значений аргументов. Может существовать N = 2 4 = 16 различных логических функций двух аргументов. Таким образом, существует 16 различных логических функций двух аргументов, каждая из которых задается своей таблицей истинности :

15 АргументыЛогические функции АВ F1F1 F2F2 F3F3 F4F4 F5F5 F6F6 F7F7 F8F8 F9F9 F10F10 F 11 F 12 F 13 F 14 F 15 F Легко заметить, что здесь логическая функция F2 является функцией логического умножения, F8 функцией логического сложения, F13 функцией логического отрицания для аргумента А и F11 функцией логического отрицания для аргумента В. В обыденной и научной речи кроме базовых логических связок «и», «или», «не» используются и некоторые другие: «если... то...», «... тогда и только тогда, когда...» и др. Некоторые из них имеют свое название и свой символ, и им соответствуют определенные логические функции.

16 ABC A B&CB&CF(A,B,C) Даны логические переменные: A, B, C. Сколько различных решений имеет данное уравнение? AB&C=0 Решение: Приведем выражение левой части уравнения к нормальной форме и приравняем к 0: A B&C=0 Составим таблицу истинности: Ответ: 3 решения

17 1. Определить количество строк и столбцов для следующей функции 2.Начертить таблицу и заполнить заголовок 3.Заполнить таблицу ABC Â B V C Â&(BvC)