Формула логики высказываний – это сложное высказывание, которое получено из простых высказываний, связанных между собой логическими операциями.
С помощью введенных операций можно строить различные булевы функции. Порядок выполнения операций указывается скобками. Для упрощения принят ряд соглашений:
1. Действия в скобках;
2. Отрицание;
3. Конъюнкция;
4. Дизъюнкция;
5. Импликация;
6. Эквивалентность.
Любая булева функция полностью определяется своей таблицей истинности.
Пример 2. Определим таблицу истинности булевой функции
Переменных: две (x и y), т.е. n = 2 Þ количество строк: 2n=22=4. с заголовком: 5
Количество столбцов: 2 переменные + 5 операций (&,, ,Ú). итого 7
Порядок операций:
4 3 5 1 2
Искомая таблица истинности:
Задача 2. Определить значение истинности высказываний:
а) 7 является простым числом, или 19 является простым числом.
б) 2 + 3 = 6, и Архангельск расположен на Северной Двине.
в) Если 12 делится на 6, то 12 делится на 4.
г) 11 делится на 3 тогда и только тогда, когда 20 делится на 5.
Решение:
а) Данное высказывание является сложным, поэтому обозначим x - 7 является простым числом, a y - 19 является простым числом. Имеем, что x = 1, y = 1. Составим формулу x v y и, используя таблицу истинности, найдем логическое значение формулы. Получим x v y = 1.
б) Данное высказывание является сложным, поэтому обозначим x - 2 + 3 = 6, а y - Архангельск расположен на Северной Двине. Имеем, что x = 0, y = 1. Составим формулу x Ù y и, используя таблицу истинности, найдем логическое значение формулы. Получим x Ù y = 0.
в) Данное высказывание является сложным, поэтому обозначим x - 12 делится на 6, a y - 12 делится на 4. Имеем, что x = 1, y = 1. Составим формулу x ® y и, используя таблицу истинности, найдем логическое значение формулы. Получим x ® y = 1.
г) Данное высказывание является сложным, поэтому обозначим x - 11 делится на 3, а y - 20 делится на 5. Имеем, что x = 0, y= I. Составим формулу x «y и, используя таблицу истинности, найдем логическое значение формулы. Получим x «y =0.
Самостоятельно задача 3. Определите истинность составного высказывания:
& ) & (C V D), состоящего из простых высказываний:
А= {Принтер – устройство вывода информации},
B= {Процессор – устройство хранения информации},
C= {Монитор – устройство вывода информации},
D= {Клавиатура – устройство обработки информации}.
Решение: сначала на основании знания устройств компьютера устанавливаем истинность простых высказываний: А=1, В=0, С=1, D=0.
Определим теперь истинность составного высказывания, используя таблицы истинноcти логических операций:
( & ) & (1 V 0) = (0 & 1) & (1 V 0) = 0
Составное высказывание ложно.
Самостоятельно задача 4.
Постройте таблицу истинности для функции F = x Ú y Ù z
Переменных:
три (x, y и z), т.е. n = 3 Þ количество строк: 2n=23=8. с заголовком: 9
Количество столбцов:
3 переменные + 3 операции (Ú,Ù,). итого 6
Порядок операций:
3 2 1
F = x Ú y Ù z
x | y | z | Øz | y Ù z | x Ú y Ù z |
Задача 5.
Даны значения: x = 0, y = 1, z = 1. Определите логические значения высказываний
(x Ù y) «(z Ú y)
(x Ù y) «(z Ú 1)
(x Ù y) «(z Ú 0)
(0 Ù 1) «(1 Ú 0)
0 «1
0 (ложь)