3 таблица истинности импликации. Оборудование и программный материал
Построение таблиц истинности сложных высказываний.
Приоритет логических операций
1) инверсия 2) конъюнкция 3) дизъюнкция 4) импликация и эквивалентность
Как составить таблицу истинности?
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.
Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре:
(0, 0), (0, 1), (1, 0), (1, 1).
Если формула содержит три переменные, то возможных наборов значений переменных восемь (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).
Количество наборов для формулы с четырьмя переменными равно шестнадцати и т. д.
Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.
Примеры.
1. Составим таблицу истинности для формулы 96%" style="width:96.0%">
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1 , то есть является тождественно истинной .
2. Таблица истинности для формулы 96%" style="width:96.0%">
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0 , то есть является тождественно ложной .
3. Таблица истинности для формулы 96%" style="width:96.0%">
Из таблицы видно, что формула 0 " style="border-collapse:collapse;border:none">
Вывод: получили в последнем столбце все единицы. Значит, значение сложного высказывания истинно при любых значениях простых высказываний К и С. Следовательно, учитель рассуждал логически правильно.
Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b).
Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записывается набор аргументов, а в правой части - соответствующие значения логической функции.
При построении таблицы истинности необходимо учитывать порядок выполнения логических операций. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке:
- 1. инверсия;
- 2. конъюнкция;
- 3. дизъюнкция;
- 4. импликация и эквивалентность.
Для изменения указанного порядка выполнения логических операций используются круглые скобки.
Предлагается следующий алгоритм построения таблицы истинности .
- 1. Определить количество наборов входных переменных - всевозможных сочетаний значений переменных, входящих в выражения, по формуле: Q=2 n , где n - количество входных переменных. Оно определяет количество строк таблицы.
- 2. Внести в таблицу все наборы входных переменных.
- 3. Определить количество логических операций и последовательность их выполнения.
- 4. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности.
Чтобы не повторить или не пропустить ни одного возможного сочетания значений входных переменных, следует пользоваться одним из предлагаемых ниже способов заполнения таблицы.
Способ 1. Каждый набор значений исходных переменных есть код числа в двоичной системе счисления, причем количество разрядов числа равно количеству входных переменных. Первый набор - число 0. Прибавляя к текущему числу каждый раз по 1, получаем очередной набор. Последний набор - максимальное значение двоичного числа для данной длины кода.
Например, для функции от трех переменных последовательность наборов состоит из чисел:
Способ 2. Для функции от трех переменных последовательность данных можно получить следующим путем:
- а) разделить колонку значений первой переменной пополам и заполнить верхнюю половину нулями, нижнюю половину единицами;
- б) в следующей колонке для второй переменной половинку снова разделить пополам и заполнить группами нулей и единиц; аналогично заполнить вторую половинку;
- в) так делать до тех пор, пока группы нулей и единиц не будут состоять из одного символа.
Способ 3. Воспользоваться известной таблицей истинности для двух аргументов. Добавляя третий аргумент, сначала записать первые 4 строки таблицы, сочетая их со значением третьего аргумента, равным 0, а затем еще раз записать эти же 4 строки, но теперь уже со значением третьего аргумента, равным 1. В результате в таблице для трех аргументов окажется 8 строк:
Например, построим таблицу истинности для логической функции:
Количество входных переменных в заданном выражении равно трем (A,B,C) . Значит, количество входных наборов Q=2 3 =8 .
Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C , промежуточных результатов и (B V C ), а также искомого окончательного значения сложного арифметического выражения:
- 0 0 0 1 0 0
- 0 0 1 1 1 1
- 0 1 0 1 1 1
- 0 1 1 1 1 1
- 1 0 0 0 0 0
- 1 0 1 0 1 0
- 1 1 0 0 1 0
- 1 1 1 0 1 0
- 7.4. Логические функции и их преобразования. Законы логики
Для операций конъюнкции, дизъюнкции и инверсии определены законы булевой алгебры, позволяющие производить тождественные (равносильные) преобразования логических выражений .
Законы логики
- 1. ¬¬ А
- 2. A&B
- 3. AVB
- 4. A&(B&C)
- 5. AV(BVC)
- 6. A&(BVC)
- 7. AV(B&C)
- 8. A&A
- 9. AVA
- 10. AV¬A
- 11. A&¬A
- 12. A&И
- 13. AVИ
- 14. A&Л
- 15. AVЛ
- 16. ¬(A&B)
- 17. ¬(AVB)
- 18. A => B
Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.
Пример 1. Упростить выражения так, чтобы в полученных формулах не содержалось отрицания сложных высказываний.
Решение
Пример 2. Минимизировать функцию
При упрощении выражения использовались формулы поглощения и склеивания.
Пример 3. Найти отрицание следующего высказывания: "Если урок будет интересным, то никто из учеников (Миша, Вика, Света) не будет смотреть в окно".
Решение
Обозначим высказывания:
Y - "Урок интересный";
M - "Миша смотрит в окно";
B - "Вика смотрит в окно";
C - "Света смотрит в окно".
При упрощении выражения использовались формула замены операций и закон де Моргана.
Пример 4. Определить участника преступления, исходя из двух посылок: логический компьютер таблица
- 1) "Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал";
- 2) "Если Иванов не участвовал, то Сидоров не участвовал".
Решение
Составим выражения:
I - "Иванов участвовал в преступлении";
P - "Петров участвовал в преступлении";
S - "Сидоров участвовал в преступлении".
Запишем посылки в виде формул:
Проверим результат, используя таблицу истинности:
Ответ: Иванов участвовал в преступлении.
Построение логической функции по ее таблице истинности
Мы научились составлять таблицу истинности для логической функции. Попробуем решить обратную задачу.
Рассмотрим строки, где значение истинности функции Z истинно (Z=1). Функцию для этой таблицы истинности можно составить следующим образом: Z(X,Y) = (¬ X& ¬Y)V(X& ¬Y).
Каждой строке, где функция истинна (равна 1), соответствует скобка, представляющая собой конъюнкцию аргументов, причем если значение аргумента О, то мы берем его с отрицанием. Все скобки соединены между собой операцией дизъюнкции. Полученную формулу можно упростить, применив законы логики:
Z(X,Y) <=> ((¬X& ¬Y) VX)&((¬X&Y)V ¬Y) <=> (XV(¬X& ¬Y)) &(¬YV(¬X&¬Y)) <=> ((XV¬X)&(XV ¬Y))&((Y¬V ¬X)&(¬YV ¬Y)) <=> (1&(XV ¬Y))&((¬YV ¬X)& ¬Y)<=> (XV ¬Y)&((¬YV ¬X)& ¬Y).
Проверьте полученную формулу: составьте таблицу истинности для функции Z(X,Y).
Запишите правила конструирования логической функции по ее таблице истинности:
- 1. Выделить в таблице истинности те строки, в которых значение функции равно 1.
- 2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
- 3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
- 4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент мы берем с отрицанием.
При составлении таблицы истинности для логического выражения необходимо:
Выяснить количество строк в таблице (вычисляется как 2 n , где n – количество переменных).
Выяснить количество столбцов (определяется как количество переменных + количество логических операций).
Установить последовательность выполнения логических операций.
Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных.
Заполнить таблицу истинности по столбцам.
Контрольный пример . Построить таблицу истинности для выражения F = (A V B) & (¬A V ¬B).
Количество строк в таблице определяется как 2 2 (2 переменных) + 1 (заголовок таблицы) = 5.
Количество столбцов – как 2 логические переменные (A, B) + 5 логических операций (&, V, ¬, →, ↔).
Расставим порядок выполнения операций:
(A V B) & (¬A V ¬B).
Построим таблицу истинности для данного логического выражения (таблица 5).
Таблица 5 – Таблица истинности для логического выражения
|
(A V B) & (¬A V ¬B) |
||||||
Контрольный пример . Построить таблицу истинности для логического выражения X V Y & ¬Z.
Количество строк = 2 3 + 1 = 9.
Количество столбцов = 3 логические переменные + 3 логических операций = 6.
Укажем порядок действий:
Нарисуем и заполним таблицу 6:
Таблица 6 – Таблица истинности для логического выражения
1.4 Построение логических схем
С точки зрения логики электрический ток либо течет, либо не течет; электрический импульс есть или нет; электрическое напряжение есть или нет. Рассмотрим электрические контактные схемы, реализующие логические операции (схемы 1 – 3). На схемах 1 – 3 контакты обозначены латинскими буквами A и B.
Схема 1 – Конъюнкция Схема 2 – Дизъюнкция Схема 3 – Инверсия
(автоматический ключ)
Схема 4 – Конъюнктор Схема 5 – Дизъюнктор Схема 6 – Инвертор
Цепь на схеме 1 с последовательным соединением контактов соответствует логической операции «И» и представляется конъюнктором (схема 4). Цепь на схеме 2 с параллельным соединением контактов соответствует логической операции «ИЛИ» и представляется дизъюнктором (схема 5). Цепь на схеме 3 (электромагнитное реле) соответствует логической операции «НЕ» и представляется инвертором (схема 6).
Именно такие электронные схемы нашли свое применение в качестве элементной базы ЭВМ. Элементы, реализующие базовые логические операции, назвали базовыми логическими элементами или вентилями и характеризуются они не состоянием контактов, а наличием сигналов на входе и выходе элемента. Их названия и условные обозначения являются стандартными и используются при составлении и описании логических схем компьютера.
Логические схемы необходимо строить из минимально возможного количества элементов, что, в свою очередь, обеспечивает большую скорость работы и увеличивает надежность устройства.
Правило построения логических схем:
Определить число логических переменных.
Определить количество базовых логических операций и их порядок.
Изобразить для каждой логической операции соответствующий ей вентиль.
Соединить вентили в порядке выполнения логических операций.
Контрольный пример. Пусть X = Истина (1), Y = Ложь (0). Составьте логическую схему для следующего логического выражения: F = X V Y & X.
1) Две переменные –X и Y.
2) Две логические операции: X V Y & X.
3) Строим схему (рисунок 3).
4) Ответ: 1 V 0 & 1 = 1.
Рисунок 3 – Логическая схема для логического выражения F = X V Y & X
Построение таблиц истинности и логических функций
Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a , b ).
Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записывается набор аргументов, а в правой части - соответствующие значения логической функции. При построении таблицы истинности необходимо учитывать порядок выполнения логических операций.
Порядок выполнения логических операций в сложном логическом выражении:
1. инверсия;
2. конъюнкция;
3. дизъюнкция;
4. импликация;
5. эквивалентность.
Для изменения указанного порядка выполнения операций используются скобки.
Алгоритм построения таблиц истинности для сложных выражений :
количество строк = 2 n + строка для заголовка ,
n - количество простых высказываний.
количество столбцов = количество переменных + количество логических операций ;
· определить количество переменных (простых выражений);
· определить количество логических операций и последовательность их выполнения.
3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.
Пример: Составить таблицу истинности логического выражения:
D = А & ( B V C )
Решение:
1. Определить количество строк:
на входе три простых высказывания: А, В, С поэтому n =3 и количество строк = 23 +1 = 9.
2. Определить количество столбцов:
простые выражения (переменные): А, В, С ;
промежуточные результаты (логические операции):
А - инверсия (обозначим через E );
B V C - операция дизъюнкции (обозначим через F );
а также искомое окончательное значение арифметического выражения:
D = А & ( B V C ) . т. е. D = E & F - это операция конъюнкции.
Заполнить столбцы с учетом таблиц истинности логических операций.
font-size:12.0pt">Построение логической функции по ее таблице истинности:
Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции Z (X ,Y ):
font-size:12.0pt">1 .
Так как строки две, получаем дизъюнкцию двух элементов: () V () .
Каждый логический элемент в этой дизъюнкции запишем в виде конъюнкции аргументов функции X и Y : ( X & Y ) V ( X & Y ).