Базовые логические функции

Начнем с того, что:

Как правило, высказывания могут быть либо истинными, либо ложными, то есть подразумевается, что алгебра логики двоична, хотя в вузе вы изучите и разделы k-значной логики. Представим высказывание:

«За окном метель»

Если за окном действительно метель, то оно истинно, а если нет – ложно. А что, если я инвертирую данное выражение: «За окном нет метели». Если за окном действительно метель, то оно станет ложным, а если нет – истинным. Теперь все наоборот, оно и логично, ведь выражение инвертировано. В алгебре логики такая операция называется инверсией или же отрицанием. Ее таблица истинности выглядит так:

Вроде все легко. Но иногда возникает необходимость использовать несколько высказываний сразу. Давай рассмотрим следующее:

«За окном метель, и я пошел на тренировку»

Два простых высказывания связаны союзом «И», что говорит нам о том, что для истинности всего высказывая необходимо выполнение всех простых. 

Если метели нет, и на тренировку я не ходил - ложь
Если метель есть, но на тренировку я не ходил - ложь
Если метели нет, но на тренировку я не ходил - ложь
А если метель есть, и на тренировку я пошел - истина

Ее таблица истинности выглядит так:

Если же мы между двумя простыми условиями поставим союз «ИЛИ» это изменит ситуацию:

«За окном метель или я пошел на тренировку»

Если метели нет и на тренировку я не ходил - ложь
Если метель есть, но на тренировку я не ходил - истина
Если метели нет, но на тренировку я не ходил - истина
А вот есть метель есть, и на тренировку я пошел - истина

Как видно, для выполнения этого условия необходимо выполнение хотя бы одного из простых условий, а логическое ИЛИ называется дизъюнкцией. Ее таблица истинности выглядит так:

Можно обратиться к их аналогам в k-значной логике,чтобы удобнее запомнить эти функции, Если хорошенько приглядеться, то можно заметить, что функция конъюнкции аналогична функции минимума из A и B, а дизъюнкция – максимуму. Попробуйте проверить самостоятельно.

В принципе, система из этих трех базовых функций (конъюнкция, дизъюнкция и инверсия) уже является полной, то есть с помощью этих 3-ех функций можно выразить все остальные. Однако для удобства существуют еще несколько. Функция следования или импликации имеет следующую таблицу:

Она довольно легко понимается на примере еды. Да-да, я обжора, но не будем отходить от темы: представим, что A – «Голоден ли я?», B – «Есть ли у меня шаурма?» Тогда существует 4 возможных варианта:

Я не голоден, и еды у меня нет ну, и наплевать, я же не голоден - истина
Я не голоден, и у меня есть еда все равно наплевать, я же не голоден - истина
Я голоден, и у меня нет еды все плохо, мне нечем перекусить - ложь
Я голоден, и у меня есть еда все хорошо, я могу перекусить - истина

Получается лишь ситуация следования из единицы в ноль дает мне ложь. Эта функция, кстати, тоже имеет аналог из математики – это <= (меньше, либо равно).
Убедись самостоятельно, таблица истинности никак не изменится. 

Еще одна довольно очевидная функция – это эквивалентность или тождество. Ну, тут все до смешного просто. Это прямой аналог функции обычного равенства: если A равно B, то результат истина, а есть нет – ложь. Вот ее таблица истинности:

Казалось бы, вроде все, но я познакомлю тебя еще с тремя функциями, взгляни на них:

Что-то страшное, в школе про них обычно не говорят, однако они существуют. Если приглядеться, то можно заметить, что функция «Исключающее или», или как ее принято обозначить XOR, – это полная противоположность эквивалентности. Их таблицы истинности полностью противоположны, и да, это так и есть, поэтому XOR всегда можно раскрыть, как отрицание эквивалентности. 

Две другие функции являются инверсиями для конъюнкции и дизъюнкции, можем это проверить самостоятельно, их таблицы истинности тоже полностью противоположны, поэтому они легко выражаются через первые 3 базовые функции.

Тогда зачем же они нужны? Они ведь просто повторяют уже известные функции. Отчасти да, но дело в том, что раз две последние функции раскрываются через отрицание, конъюнкцию и дизъюнкцию, то они образуют базис, то есть с помощью любой из этих операций, можно выразить любую другую функцию. А вот где данные функции бывают полезны, вы уже узнаете на курсе дискретной математики в вузе.