Матлог / Matematicheskaya_logika

Булевы функции от двух переменных

Булевы функции от двух переменных взаимосвязаны следующими свойствами:

Система булевых функций

Система булевых функций называется замкнутой, если суперпозиции из 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 называется сокращенной ДНФ.

Лемма: Любая ДНФ р эквивалентна некоторой сокращенной ДНФ.

Понятие предиката

Перенесение на предикаты логических операций

Множество истинности предикатов, полученных при помощи логических операций