- •МАТЕМАТИЧЕСКАЯ ЛОГИКА
- •Истинностные значения формул логики высказываний
- •Истинностные таблицы формул логики высказываний
- •Отношение равносильности формул
- •Отношение равносильности формул
- •Истинностные функции
- •Логические функции одной переменной
- •Логические функции двух переменных
- •Дизъюнктивно-нормальная форма
- •Элементарной конъюнкцией (дизъюнкцией) называется выражение, состоящее из конечного числа переменных и их отрицаний,
- •Алгоритм приведения к СДНФ
- •Конъюнктивно-нормальная форма
- •Алгоритм приведения к СКНФ
- •Любая булева функция, не являющаяся тождественным нулём или единицей, имеет только одну СДНФ
- •СДНФ: по
- •СКНФ: по
- •Существование СДНФ позволяет провести процедуру, называемую разложением булевой
- •Задача. По заданной таблице истинности найти логическую функцию.
- •Теорема.
- •Полные системы истинностных функций
- •Теорема. Системы истинностных функций { , }, { , }, { , }
- •Стрелка Пирса (символ Лукашевича)
- •Стрелка Пирса (символ Лукашевича)
- •Штрих Шеффера
- •Штрих Шеффера
- •Виды формул алгебры высказываний
- •Спасибо за внимание!!!
- •Определить, являются ли равносильными формулы.
- •Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту
- •Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту
МАТЕМАТИЧЕСКАЯ ЛОГИКА
Лекция 2. Истинностные функции логики высказываний
1.Истинностные значения и истинностные таблицы формул логики высказываний
2.Отношение равносильности формул
3.Истинностные функции
4.Совершенные нормальные формы истинностных функций
5.Полные системы истинностных функций
6.Классификация формул логики высказываний
Истинностные значения формул логики высказываний
Истинностные таблицы формул логики высказываний
Таблица, содержащая всевозможные интерпретации формулы и соответствующие этим интерпретациям значения формулы, называется истинностной таблицей формулы.
Отношение равносильности формул
Отношение равносильности формул
Истинностные функции
Логические функции одной переменной
x |
F1 |
F2 |
|
F3 |
|
F4 |
|
|
|||||
|
|
|||||
|
|
|||||
|
|
0 |
0 |
0 |
|
1 |
|
1 |
|
|
|||||
|
|
1 |
0 |
1 |
|
|
|
0 |
|
|
|
|
1 |
|
|
|
|
||||||||
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Логические функции двух переменных
Двухместных истинностных функций - 16
x1 |
x2 |
F1 |
F2 |
F3 |
F4 |
F5 |
F6 |
F7 |
F8 |
F9 |
F10 |
F11 |
F12 |
F13 |
F14 F15 |
F16 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Число п-местных истинностных функций |
2 |
(2 |
n |
) |
равно |
|
|||
|
|
|
|
Дизъюнктивно-нормальная форма
ДНФ — является логической суммой элементарных конъюнкций.
Совершенная ДНФ – логическая сумма элементарных конъюнкций, в каждой из которых присутствуют все переменные данной функции.
Элементарной конъюнкцией (дизъюнкцией) называется выражение, состоящее из конечного числа переменных и их отрицаний, взятых в этом выражении не более одного раза и разделённых операциями конъюнкции (дизъюнкции):
s |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xi |
|
|
|
|
|
|
||||
|
|
|
|
x x |
|
x3 |
||||||||
yi |
|
yi xi |
|
2 |
||||||||||
|
|
1 |
|
|
|
|
||||||||
|
, где |
или |
, например |
- элементарная |
||||||||||
i 1 конъюнкция; |
|
|
|
|
|
|
|
|
|
|
|
|||
s |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
yi |
, |
где |
или ,например |
- элементарная |
||||||||||
|
|
yi xi |
|
|
xi |
x1 |
x2 x3 |
|||||||
i 1 |
дизъюнкция; |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|