- •МАТЕМАТИЧЕСКАЯ ЛОГИКА
- •Истинностные значения формул логики высказываний
- •Истинностные таблицы формул логики высказываний
- •Отношение равносильности формул
- •Отношение равносильности формул
- •Истинностные функции
- •Логические функции одной переменной
- •Логические функции двух переменных
- •Дизъюнктивно-нормальная форма
- •Элементарной конъюнкцией (дизъюнкцией) называется выражение, состоящее из конечного числа переменных и их отрицаний,
- •Алгоритм приведения к СДНФ
- •Конъюнктивно-нормальная форма
- •Алгоритм приведения к СКНФ
- •Любая булева функция, не являющаяся тождественным нулём или единицей, имеет только одну СДНФ
- •СДНФ: по
- •СКНФ: по
- •Существование СДНФ позволяет провести процедуру, называемую разложением булевой
- •Задача. По заданной таблице истинности найти логическую функцию.
- •Теорема.
- •Полные системы истинностных функций
- •Теорема. Системы истинностных функций { , }, { , }, { , }
- •Стрелка Пирса (символ Лукашевича)
- •Стрелка Пирса (символ Лукашевича)
- •Штрих Шеффера
- •Штрих Шеффера
- •Виды формул алгебры высказываний
- •Спасибо за внимание!!!
- •Определить, являются ли равносильными формулы.
- •Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту
- •Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту
Теорема. Системы истинностных функций { , }, { , }, { , } – полные.
Стрелка Пирса (символ Лукашевича)
•логическая операция с двумя переменными, соответствует обороту
речи «ни…, ни…», обозначается следующим образом: F (A, B) A B
•Выражение A B истинно в том и только в том случае, когда оба высказывания A и B ложны.
Стрелка Пирса (символ Лукашевича)
A B A B
A A A
A B (A B) (A B)
A B A↓B 0 0 1 0 1 0 1 0 0 1 1 0
A B (A A) (B B)
Штрих Шеффера
•логическая операция с двумя переменными, соответствует обороту речи «не… или не…», обозначается
следующим образом F (A, B) A B
•Выражение A|B ложно в том и только в том случае, когда оба высказывания A и B истинны.
Штрих Шеффера
A B A B
A A A
A B (A B) (A B)
A B (A A) (B B)
A B A|B 0 0 1 0 1 1 1 0 1 1 1 0
Теорема. Системы истинностных функций {|} и { }– полные.
Виды формул алгебры высказываний
Формула А называется
• общезначимой (тождественно истинной, тавтологией), если во всех своих интерпретациях она принимает значение И
•невыполнимой (тождественно ложной, противоречием), если во всех своих интерпретациях она принимает значение Л
•нейтральной, если она не является ни общезначимой, ни ложной
•выполнимой, если она общезначимая или нейтральная
•необщезначимой, если она невыполнимая или нейтральная.
Спасибо за внимание!!!
Определить, являются ли равносильными формулы.
Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию.
|
A |
B |
C |
F(A, B, C) |
|
0 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
1 |
|
|
0 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
|
x1 |
x2 |
x3 |
F(x1, x2, x3) |
0 |
0 |
0 |
0 |
|
|
|
|
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
0 |
1 |
1 |
0 |
|
|
|
|
1 |
0 |
0 |
1 |
|
|
|
|
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
|
|
|
|
1 |
1 |
1 |
1 |
|
|
|
|