Формулы логики высказываний
Формула логики высказываний – это сложное высказывание, которое получено из простых высказываний, связанных между собой логическими операциями.
С помощью введенных операций можно строить различные булевы функции. Порядок выполнения операций указывается скобками. Для упрощения принят ряд соглашений:
1. Действия в скобках;
2. Отрицание;
3. Конъюнкция;
4. Дизъюнкция;
5. Импликация;
6. Эквивалентность.
Любая булева функция полностью определяется своей таблицей истинности.
Примеры. 1) Представить логическими формулами следующие высказывания: «Если допоздна работаешь с компьютером и при этом пьешь много кофе, то утром просыпаешься в дурном настроении или с головной болью».
Решение. Пусть: А—«допоздна работаешь с компьютером»,
В—«пьешь много кофе»,
С—«утром просыпаешься в дурном настроении»,
D—«утром просыпаешься с головной болью».
Тогда сложное высказывание «Если допоздна работаешь с компьютером и при этом пьешь много кофе, то утром просыпаешься в дурном настроении или с головной болью» представим формулой: (A&B)→(CÚD)
2) Определить
таблицу истинности булевой функции
Алгоритм построения таблицы истинности:
1) Определить число строк (оно вычисляется по формуле k = 2n, где k – количество строк, а n – число различных пропозициональных переменных, входящих в формулу).
2) Задать все комбинации совместной истинности/ложности переменных.
3) Вычислить (построчно) значение каждой подформулы и формулы в целом (используя приведенные выше определения каждой логической операции).
Переменных: две (x и y), т.е. n=2, количество строк: k=2n=22=4. с заголовком: 5
Количество
столбцов: 2
переменные + 5 операций (&,¬,
¬,Ú).
итого 7
Порядок операций:
4 3 5 1 2
x&¬y→(¬xÚy)
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
В этой таблице всего четыре строки, поскольку формула содержит лишь две переменные – x и y. Первые два столбца задают все возможные комбинации совместной истинности и ложности этих переменных. Следующие пять столбцов показывают, каким будет значение каждой подформулы в той или иной строчке. Последний (результирующий) столбец показывает значение всей формулы в целом.
3) Построить таблицу истинности для функции F = XÚY&¬Z
Переменных: три (X, Y и Z), т.е. N = 3, следовательно количество строк: 2n=23=8. С заголовком: 9
Количество столбцов: 3 переменные + 3 операции (Ú, &,¬). итого 6
Порядок операций: F = X Ú Y & ¬Z
3 2 1
X |
Y |
Z |
¬Z |
Y & ¬Z |
X Ú Y & ¬Z |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
4) Определить значение истинности высказываний:
а) 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.
5) Определите истинность составного высказывания:
&
)
& (C
Ú
D),
состоящего из простых высказываний:
А= {Принтер – устройство вывода информации},
B= {Процессор – устройство хранения информации},
C= {Монитор – устройство вывода информации},
D= {Клавиатура – устройство обработки информации}.
Решение: сначала на основании знания устройств компьютера устанавливаем истинность простых высказываний: А=1, В=0, С=1, D=0.
Определим теперь истинность составного высказывания, используя таблицы истинноcти логических операций:
(
&
)
& (1 Ú
0) = (0 & 1) & (1 Ú
0) = 0. Составное высказывание ложно.
6) Даны значения: x = 0, y = 1, z = 1.Определите логические значения высказывания: (x & y) « (z V ¬y).
Решение: (x & y) « (z V ¬1)
(x & y) « (z V 0)
(0 & 1) « (1 V 0)
0 « 1
0 (ложь).