Целесообразно вначале искать покрывающий интервал для максимального элемента булева пространства, у которого меньше взято соседей. Затем, что одна и та же клетка матрицы может входить в несколько интервалов.
_
Элемент х1х2х3х4 склеиваем с элементом х1х2х3х4 по переменной х4 Покрывающий их интервал соответствует элементарной конъюнкции
_
<х1х2х3>.
_ _ |
_ |
_ |
|
Окончательно, получаем минимальную ДНФ |
х1х2х3V х1 х2х4 V х3х4 V |
х1х2х3 |
|
4.Элементы математической логики
4.1.Алгебра высказываний 4.2. Логические отношения
4.3.Проверка правильности рассуждений
4.4.Нормальные формы формул алгебры высказываний.
4.5.Моделирование алгебры высказывания с помощью релейно-контактных схем
4.6.Решение логических задач методом характеристичесого уравнения.
Математическая логика представляет собой формальный математический аппарат, изучающий различные способы логических рассуждений.
Простейшей из формальных логических теорий называют алгебру высказываний. Исчисление высказываний следующая ступень в иерархии формальных теорий. Ещё выше стоят алгебра предикатов и исчисление предикатов.
4.1 Алгебра высказываний
Высказывание – некоторое утверждение, относительно которого нас интересует только его истинность или ложность.
Высказывание называют простым (элементарным), если его истинность не зависит от истинности других высказываний.
Высказывание называют сложным (составным), если оно зависит от истинности других высказываний.
В алгебре высказываний объектом исследования является множество высказываний, а операциями – некоторые логические операции, каждую из которых можно рассматривать как некоторое сложное высказывание.
Определяются эти операции следующими таблицами истинности. Например, операции «дизъюнкция» соответствует сложное высказывание, которое ложно тогда и только тогда, когда A ложно и B ложно
A |
B |
A\/B |
|
|
|
Л |
Л |
Л |
|
|
|
Л |
И |
И |
|
|
|
И |
Л |
И |
|
|
|
И |
И |
И |
|
|
|
В дальнейшем каждое простое высказывание можно связать с некоторой двоичной переменной.
Поэтому сложное высказывание можно связать с некоторой двоичной (логической) функцией.
Используя подобную связь можно сказать, что алгебра высказываний есть одна из интерпретаций алгебры логических функций.
Запишем таблицу истинности операций алгебры высказываний:
A |
B |
A\/B |
A/\B |
AÆB |
A B |
A B |
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
|
|
|
|
|
|
|
Любое сложное высказывание можно представить в виде некоторой формулы. Дадим определение формулы:
1.Каждый символ a, b, c… есть формула;
2.Если А и В – формулы, то формулами являются А*В, А\/В, где * - любая операция из других формул нет.
Для установления порядка выполнения операций в формулах используются скобки. При их отсутствии порядок устанавливается приоритетом операций
Вычисление по формуле продемонстрируем на следующем примере:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
b |
c |
a b |
(a b)c |
((a b)c) |
a |
a \/ bc |
F |
||
|
|
|
|
|
|
|
|
|
1 |
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|||
|
|
|
|
|
|
|
|
|
1 |
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|||
|
|
|
|
|
|
|
|
|
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|||
|
|
|
|
|
|
|
|
|
|
|