Матлог / Matematicheskaya_logika
.pdfБулевы функции от двух переменных
Булевы функции от двух переменных взаимосвязаны следующими свойствами:
Система булевых функций
Система булевых функций называется замкнутой, если суперпозиции из F дают функцию из F.
Переключательные схемы
1 – протекание тока в проводниках
0 – отсутствие тока в проводниках
Переключатель – электромагнитое реле с контактами индукционной катушкой, состояние которой моделируется булевой переменной x: x = 1 – в катушке идет ток, x = 0 – в катушке тока нет.
Через замыкающий контакт реле ток проходит в том и только в том случае, если x = 1 – такой контакт моделируется булевой переменной x.
Через размыкающий контакт ток проходит в том и только в том случае, если x = 0 – такой контакт моделируется булевой переменной x'.
Через последовательно соединенные переключатели p,q ток проходит в том и только в том случае, если p = q = 1 – такое соединение моделируется булевым многочленом p*q.
Через параллельно соединенные переключатели p,q ток не проходит в том и только в том случае, если p = q = 0 – такое соединение моделируется булевым многочленом p + q.
ПС, моделирующая сложение трех двоичных цифр называется сумматором. Такая ПС имеет три входа a1,a2,a3 и два выхода ̅(a1,a2,a3) и ̅(a1,a2,a3), которые описывают два разряда суммы a1+a2+a3
Минимизация булевых многочленов
P – булев многочлен в форме ДНФ.
Дизъюнкция всех простых импликант формы p называется сокращенной ДНФ.
Лемма: Любая ДНФ р эквивалентна некоторой сокращенной ДНФ.
Понятие предиката
Перенесение на предикаты логических операций
Множество истинности предикатов, полученных при помощи логических операций