ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.01.2024
Просмотров: 321
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
1(F2F3))F4).
Привести формулу к виду КНФ:
1) F=(F1(F2 F3))F4 ;
2) F=(F1(F2F3))F4 ;
3) F=(F1( F2) F3)F4 ;
4) F=(F4F1)(F4(F2)F3);
5) F=(F4F1)(F4F2)(F4F3).
Пример: Дана формула F=((F1F2)(F1F2)).
Привести формулу к виду ДНФ:
Если каждая элементарная конъюнкция (или элементарная дизъюнкция) формулы содержат символы всех пропозициональных переменных, то такая формула называется совершенной. Есть совершенные дизъюнктивные нормальные формы формулы (СДНФ) и совершенные конъюнктивные нормальные формы формулы (СКНФ).
1.1.5.2 Алгоритм преобразования ДНФ к виду СДНФ.
Шаг 1: если в элементарную конъюнкцию F не входит подформула Fi или Fi, то дополнить элементарную конъюнкцию высказыванием (FiFi) и выполнить преобразование формулы по закону дистрибутивности:
F(FiFi)= FFiFFi;
Шаг 2: если в элементарную конъюнкцию F не входит подформула Fj или Fj, то повторить шаг 1, иначе – конец.
Пример: Дано F=F1F2F1F3F4F1F2F3F4.
Преобразовать формулу к виду СДНФ:
1) F=F1F2(F3F3) F1F3F4(F2F2) F1F2F3F4;
2) F=F1F2F3F1F2F3F1F2F3F4F1F2F3F4 F1F2F3F4;
4) F=(F1F2F3F4)(F1F2F3F4)(F1F2F3F4)
(F
1F2F3F4) (F1F2F3F4) (F1F2F3F4) (F1F2F3F4).
1.1.5.3 Алгоритм преобразования КНФ к виду СКНФ.
Шаг 1: если в элементарную дизьюнкцию F не входит подформула Fi или Fi, то дополнить элементарную дизьюнкцию высказыванием (FiFi) и выполнить преобразование формулы по закону дистрибутивности:
F(Fi Fi) = (F Fi)(FFi);
Шаг 2: если в элементарную конъюнкцию F не входит подформула Fj или Fj, то повторить шаг 1, иначе – конец.
Пример: Дано F=(F1F2)(F1F2F3F4).
Преобразовать формулу к виду СКНФ:
Совершенные нормальные формы формул удобно записывать, используя таблицы истинности, по значениям пропозициональных переменных и значению описываемой формулы.
Элементарные коньюнкции СДНФ формируются для значений формулы “и”. Число элементарных коньюнкций равно числу истинных значений формулы. Пропозициональные переменные, входящие в элементарную коньюнкцию, записываются без изменений, если их значение равно “и” и с логической связкой “”, если их значение равно “л”.
Элементарные дизьюнкции СКНФ формируются для значений формулы “л”. Число элементарных дизьюнкций равно числу ложных значений формулы. Пропозициональные переменные, входящие в элементарную дизьюнкцию, записываются без изменений, если их значение равно “л” и с логической связкой “”, если их значение равно “и”.
П
ример: Записать СДНФ и СКНФ для функции, заданной таблицей истинности
a) Формула СДНФ:
F(A,B,C) = АBCАBC
АBCАBC;
b) Формула СКНФ:
F(A,B,C) = (ABC) (ABC)
(ABC) (ABC).
1.2 Исчисление высказываний
Определение исчисления высказываний, как и любой формальной системы, следует начинать с задания множества аксиом и правил вывода, обеспечивающих последовательное их использование при доказательстве истинности заключения.
Доказательством называют конечную последовательность высказываний, каждое из которых является либо аксиомой, либо выводится из одного или более предыдущих высказываний этой последовательности по правилам вывода.
Определение минимально возможного множества аксиом определяет семантическую полноту исчисления, а определение правил, обеспечивающих последовательное использование аксиом и промежуточных высказываний в процессе формирования заключения – метод дедуктивного вывода.
1.2.1 Интерпретация формул
Если дана некоторая формула F и каждой ее пропозициональной переменной приписано значение "и" или "л", то говорят что дана интерпретация формулы F.
Все множество формул логики высказываний можно разбить на три класса: тождественно истинные, тождественно ложные и теоремы. В каждом классе может быть перечислимое и счетное множество формул.
Тождественно истинные формулы (или общезначимые)– это особый класс формул, которые принимают значение “истины” при любом значении пропозициональных переменных, входящих в эту формулу. Эти формулы играют роль аксиом и законов логики высказываний.
Тождественно ложные формулы (или противоречия)- это особый класс формул, которые принимают значение “ложь” при любых значениях пропозициональных переменных, входящих в формулу.
Выполнимые формулы
- это особый класс формул, которые принимают значения “истина” или “ложь” в зависимости от значений пропозициональных переменных.
Поиск алгоритма, определяющего к какому классу принадлежит та или иная формула, формирует проблему разрешимости исчисления высказываний.
Пример: Определить, к какому классу относятся формулы:
a) F = ((AB)(AC)(A(BC))
Формула принадлежит классу тождественно истинных формул (см. столбец 9).
б) F=A (BC) (AB) (AC)
Привести формулу к виду КНФ:
1) F=(F1(F2 F3))F4 ;
2) F=(F1(F2F3))F4 ;
3) F=(F1( F2) F3)F4 ;
4) F=(F4F1)(F4(F2)F3);
5) F=(F4F1)(F4F2)(F4F3).
Пример: Дана формула F=((F1F2)(F1F2)).
Привести формулу к виду ДНФ:
-
F=(F1F2)(F1F2); -
F=((F1F2)F1) ((F1F2) F2); -
F=(F1F1)(F2F1) (F1F2) (F2 F2); -
F=(F2F1) (F1F2).
Если каждая элементарная конъюнкция (или элементарная дизъюнкция) формулы содержат символы всех пропозициональных переменных, то такая формула называется совершенной. Есть совершенные дизъюнктивные нормальные формы формулы (СДНФ) и совершенные конъюнктивные нормальные формы формулы (СКНФ).
1.1.5.2 Алгоритм преобразования ДНФ к виду СДНФ.
Шаг 1: если в элементарную конъюнкцию F не входит подформула Fi или Fi, то дополнить элементарную конъюнкцию высказыванием (FiFi) и выполнить преобразование формулы по закону дистрибутивности:
F(FiFi)= FFiFFi;
Шаг 2: если в элементарную конъюнкцию F не входит подформула Fj или Fj, то повторить шаг 1, иначе – конец.
Пример: Дано F=F1F2F1F3F4F1F2F3F4.
Преобразовать формулу к виду СДНФ:
1) F=F1F2(F3F3) F1F3F4(F2F2) F1F2F3F4;
2) F=F1F2F3F1F2F3F1F2F3F4F1F2F3F4 F1F2F3F4;
-
F=F1F2F3(F4F4)F1F2F3(F4F4)F1F2F3F4 F1F2F3F4 F1F2F3F4;
4) F=(F1F2F3F4)(F1F2F3F4)(F1F2F3F4)
(F
1F2F3F4) (F1F2F3F4) (F1F2F3F4) (F1F2F3F4).
1.1.5.3 Алгоритм преобразования КНФ к виду СКНФ.
Шаг 1: если в элементарную дизьюнкцию F не входит подформула Fi или Fi, то дополнить элементарную дизьюнкцию высказыванием (FiFi) и выполнить преобразование формулы по закону дистрибутивности:
F(Fi Fi) = (F Fi)(FFi);
Шаг 2: если в элементарную конъюнкцию F не входит подформула Fj или Fj, то повторить шаг 1, иначе – конец.
Пример: Дано F=(F1F2)(F1F2F3F4).
Преобразовать формулу к виду СКНФ:
-
F=(F1F2F3F3) (F1F2F3F4); -
F=(F1F2F3) (F1F2F3) (F1F2F3F4); -
F=(F1F2F3F4F4)(F1F2F3F4F4) (F1F2F3F4); -
F=(F1F2F3F4)(F1F2F3F4)(F1F2F3F4) (F1F2F3F4) (F1F2F3F4).
Совершенные нормальные формы формул удобно записывать, используя таблицы истинности, по значениям пропозициональных переменных и значению описываемой формулы.
Элементарные коньюнкции СДНФ формируются для значений формулы “и”. Число элементарных коньюнкций равно числу истинных значений формулы. Пропозициональные переменные, входящие в элементарную коньюнкцию, записываются без изменений, если их значение равно “и” и с логической связкой “”, если их значение равно “л”.
Элементарные дизьюнкции СКНФ формируются для значений формулы “л”. Число элементарных дизьюнкций равно числу ложных значений формулы. Пропозициональные переменные, входящие в элементарную дизьюнкцию, записываются без изменений, если их значение равно “л” и с логической связкой “”, если их значение равно “и”.
П
| A | B | C | F(A,B,C) |
| Л | Л | Л | И |
| Л | Л | И | Л |
| Л | И | Л | Л |
| Л | И | И | И |
| И | Л | Л | И |
| И | Л | И | Л |
| И | И | Л | Л |
| И | И | И | И |
ример: Записать СДНФ и СКНФ для функции, заданной таблицей истинности
a) Формула СДНФ:
F(A,B,C) = АBCАBC
АBCАBC;
b) Формула СКНФ:
F(A,B,C) = (ABC) (ABC)
(ABC) (ABC).
1.2 Исчисление высказываний
Определение исчисления высказываний, как и любой формальной системы, следует начинать с задания множества аксиом и правил вывода, обеспечивающих последовательное их использование при доказательстве истинности заключения.
Доказательством называют конечную последовательность высказываний, каждое из которых является либо аксиомой, либо выводится из одного или более предыдущих высказываний этой последовательности по правилам вывода.
Определение минимально возможного множества аксиом определяет семантическую полноту исчисления, а определение правил, обеспечивающих последовательное использование аксиом и промежуточных высказываний в процессе формирования заключения – метод дедуктивного вывода.
1.2.1 Интерпретация формул
Если дана некоторая формула F и каждой ее пропозициональной переменной приписано значение "и" или "л", то говорят что дана интерпретация формулы F.
Все множество формул логики высказываний можно разбить на три класса: тождественно истинные, тождественно ложные и теоремы. В каждом классе может быть перечислимое и счетное множество формул.
Тождественно истинные формулы (или общезначимые)– это особый класс формул, которые принимают значение “истины” при любом значении пропозициональных переменных, входящих в эту формулу. Эти формулы играют роль аксиом и законов логики высказываний.
Тождественно ложные формулы (или противоречия)- это особый класс формул, которые принимают значение “ложь” при любых значениях пропозициональных переменных, входящих в формулу.
Выполнимые формулы
- это особый класс формул, которые принимают значения “истина” или “ложь” в зависимости от значений пропозициональных переменных.
Поиск алгоритма, определяющего к какому классу принадлежит та или иная формула, формирует проблему разрешимости исчисления высказываний.
Пример: Определить, к какому классу относятся формулы:
a) F = ((AB)(AC)(A(BC))
-
A
B
C
AB
AC
BC
45
16
78
1
2
3
4
5
6
7
8
9
Л
Л
Л
И
И
Л
И
И
И
Л
Л
И
И
И
Л
И
И
И
Л
И
Л
И
И
Л
И
И
И
Л
И
И
И
И
И
И
И
И
И
Л
Л
Л
Л
Л
Л
Л
И
И
Л
И
Л
И
Л
Л
Л
И
И
И
Л
И
Л
Л
Л
Л
И
И
И
И
И
И
И
И
И
И
Формула принадлежит классу тождественно истинных формул (см. столбец 9).
б) F=A (BC) (AB) (AC)
-
A
A б) F = (A(BC)(AB)(AC)). A
B
C
23
14
12
13
56
87
1
2
3
4
5
6
7
8
9
Л
Л
Л
И
Л
И
И
Л
Л
Л
Л
И
И
Л
И
И
Л
Л
Л
И
Л
И
Л
И
И
Л
Л
Л
И
И
Л
Л
И
И
Л
Л
И
Л
Л
И
И
Л
Л
Л
Л
И
Л
И
И
И
Л
Л
Л
Л
И
И
Л
И
И
И
Л
И
Л
И
И
И
Л
Л
И
И
Л
Л