ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.01.2024
Просмотров: 320
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Формула принадлежит классу тождественно ложных формул (см. столбец 9).
в) F = (AB)(BC).
-
Формула принимает значение “и” или “л” для различных наборов значений
A
B
C
12
23
45
1
2
3
4
5
6
Л
Л
Л
Л
И
Л
Л
Л
И
Л
И
Л
Л
И
Л
И
И
И
Л
И
И
И
Л
Л
И
Л
Л
И
И
И
И
Л
И
И
И
И
И
И
Л
И
И
И
И
И
И
И
Л
Л
Любая формула исчисления высказываний может рассматриваться как формула алгебры высказываний и, следовательно, можно рассматривать ее логические значения на различных наборах значений входящих в нее пропозициональных переменных по таблицам истинности.
Недостаток использования таблиц истинности состоит в том, что при большом числе пропозициональных переменных сама процедура построения этих таблиц становится громоздкой, так как число строк этой таблицы равно 2n , где n - число пропозициональных переменных формулы, а число столбцов не меньше (n+m), где m – число логических связок в формуле.
Пример: В семье есть договоренность относительно пользования телевизором на субботние вечера: а) если не смотрит отец(А), то смотрит дочь (C) и не смотрит мать (В), т.е. F1=(АCВ);б) если не смотрит дочь (C), то смотрит мать (В) и не смотрит отец (А), т.е. F2=(CBA); в) если смотрит отец (A), то не смотрит дочь (C), т.е. F3=( AC). В каком случае совместимы эти условия? [2]
Формальная запись этого суждения имеет вид:
F=F1F2F3=(АCВ)(CBA)(AC).
-
Анализ таблицы показывает (см. столбец 9), что эти условия совместимы (см. строку 2), когда А=л, В=л и С=и (см. строку 2).
A
B
C
32
14
21
36
13
578
1
2
3
4
5
6
7
8
9
Л
Л
Л
Л
Л
Л
Л
И
Л
Л
Л
И
И
И
Л
И
И
И
Л
И
Л
Л
Л
И
И
И
Л
Л
И
И
Л
Л
И
И
И
Л
И
Л
Л
Л
И
Л
Л
И
Л
И
Л
И
И
И
Л
И
Л
Л
И
И
Л
Л
И
Л
Л
И
Л
И
И
И
Л
И
Л
И
Л
Л
1.2.2 Аксиомы исчисления высказываний
Как уже отмечалось множество формул, удовлетворяющих условиям тождественной истинности, бесконечно. Однако в качестве аксиом всегда выбирают только такие, которые при истинности посылок обеспечивают дедуктивный вывод истинности заключения. При этом стремятся создать такую систему аксиом, которая содержала бы минимальное число формул для заданного набора логических связок. Так известна система, которая для логических связок импликации и отрицания содержит только три аксиомы, а для логических связок импликации и дизъюнкции только пять аксиом. Для полного набора логических связок: импликация, отрицание, конъюнкция и дизъюнкция система содержит десять аксиом. В силу полноты систем, использующих логические связки а) импликации и отрицания, б) импликации и дизъюнкции, в) импликации, отрицания, конъюнкции и дизъюнкции можно использовать в процессе дедуктивного вывода любую из указанных систем.
Ниже приведена одна из систем аксиом:
А1. F1(F2F1);
А2. (F1F2)((F2F3))(F1F3));
А3. (F1 F2)F1;
А4. (F1 F2)F2;
А5. F1(F2(F1F2));
А6. F1(F1F2);
А7. F2(F1F2);
А8. (F1F3)((F2F3)((F1F2)F3));
А9. (F1F2)(( F1 F2) F1);
A10. (F1F2)((F1F3)(F2F3));
A11. (F1 F2)((F1F3)(F2F3));
А12. F1 F1.
Для проверки тождественной истинности аксиом рассмотрим таблицы истинности для A2 и A8:
А2. (F1 F2)(( F1( F2 F3))( F1 F3))
-
F1
F2
F3
12
13
23
16
75
48
1
2
3
4
5
6
7
8
9
л
л
л
и
и
и
и
и
и
л
л
и
и
и
и
и
и
и
л
и
л
и
и
л
и
и
и
л
и
и
и
и
и
и
и
и
и
л
л
л
л
и
и
л
и
и
л
и
л
и
и
и
и
и
и
и
л
и
л
л
л
и
и
и
и
и
и
и
и
и
и
и
1 2 3 4 5 6 7 8 9 10 ... 14
А8. (F1 F3)(( F2 F3)(( F1 F2) F3))
-
F1
F2
F3
1 2
13
23
43
67
58
1
2
3
4
5
6
7
8
9
л
л
л
л
и
и
и
и
и
л
л
и
л
и
и
и
и
и
л
и
л
и
и
л
л
и
и
л
и
и
и
и
и
и
и
и
и
л
л
и
л
и
л
л
и
и
л
и
и
и
и
и
и
и
и
и
л
и
л
л
л
и
и
и
и
и
и
и
и
и
и
и
.
1.2.3 Правила вывода
Выводом формулы В из множества формул F1; F2; . . . Fn называется такая последовательность формул
, что любая Fi есть либо аксиома, либо непосредственно выводима из подмножества предшествующих ей формул F1; F2; . . . Fn.
В этом случае формулу B называют заключением, а последовательность формул F1; F2; . . . Fn, сформированная отношением логического вывода, представляет схему дедуктивного вывода.
Схему дедуктивного вывода записывают так:
F1; F2; . . . Fn B,
где символ означает “верно, что B выводима из F1; F2;... Fn“.
Есть определенная связь между отношением логического вывода в схеме дедукивного вывода и импликацией в схеме закона алгебры высказываний .
Этот факт записывают так:
F1F2. . . FnB.
Известна другая форма записи дедуктивного вывода формулы В:
F
1; F2; . . . Fn B,
где над чертой записывают множество посылок и аксиом F1; F2;...Fn, а под чертой заключение В, принимающее значение “истины” при истинности всех посылок.
1.2.3.1 Правила подстановки
Если выводимая формула F содержит некоторую переменную A (обозначим этот факт F(A)) и существует произвольная формула B, то формула F(B), получающаяся заменой всех вхождений A на формулу B, также выводима в исчислении высказываний. Этот факт формально описывают так:
Этот факт записывают так:
АВF(А)
F(В).Если F(A)=A, то АВА
В.Если F (A), то АВF(А)
F(В).Следует еще раз обратить внимание, что формула F должна быть выводимой в исчислении высказываний.
Пример: Пусть даны формулы F=ACA и B=CA.
Если выполнить подстановку формулы B в формулу F вместо формулы A, то получим новую формулу F`.
А
CA (ACA)(CA)C(CA).
-
Проверим значения двух формул F и F’по таблицам истинности.
Выделенные столбцы показывают тождество двух формул.
A
B
C
13
41
31
63
76
1
2
3
4
5
6
7
8
л
л
л
л
и
и
л
и
л
л
и
л
и
и
и
и
л
и
л
л
и
и
л
и
л
и
и
л
и
и
и
и
и
л
л
л
и
и
л
и
и
л
и
и
и
л
л
и
и
и
л
л
и
и
л
и
и
и
и
и
и
л
л
и