Алгебра логики

Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями. Высказывания могут быть только истинными или ложными.

Определение

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказывания строятся над множеством {B,  ,  ,  , 0, 1}, где B — непустое множество, над элементами которого определены три операции:

 отрицание (унарная операция),

 конъюнкция (бинарная),

 дизъюнкция (бинарная),

а также константы — логический ноль 0 и логическая единица 1.

Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например  ). Конъюнкт — пропозициональная формула, являющаяся конъюнкциейодного или более литералов (например  ).

Аксиомы

1. , 

Логические операции

Простейшим и наиболее широко применяемым примером такой  алгебраической системы является множество B, состоящее всего из двух элементов:

B = { Ложь, Истина }

Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.

Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты. Также вводятся дополнительные операции, такие как эквивалентность   («тогда и только тогда, когда»), импликация   («следовательно»), сложение по модулю два  («исключающее или»), штрих Шеффера  , стрелка Пирса   и другие.

Логика  высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция   приобретает смысл вычитания из единицы;   — немодульного сложения; & — умножения;   — равенства;   — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR);   — непревосходства суммы над 1 (то есть A   B = (A + B) <= 1).

Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных для  логики высказываний аксиом. Это позволило  рассматривать, например, логику кубитов, тройственную логику (когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено») и др.

Свойства логических операций

    В алгебре логики выполняются следующие  основные законы, позволяющие производить тождественные преобразования логических выражений:

ОСНОВНЫЕ  ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

 

Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна - Мак-Класки

История

Своим существованием наука «алгебра логики» обязана  английскому математику Джорджу Булю, который исследовал логику высказываний. Первый в России курс по алгебре логики был прочитанП.С. Порецким в Казанском государственном университете.

 
 
 
 
 
 
 
 
 
 

Переключательная  схема.

    В компьютерах и других автоматических устройствах широко применяются  электрические схемы, содержащие сотни  и тысячи переключательных элементов: реле, выключателей и т.п. Разработка таких схем весьма трудоёмкое дело. Оказалось, что здесь с успехом  может быть использован аппарат  алгебры логики.

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

    Будем считать, что два переключателя Х и   связаны таким образом, что когда Х замкнут, то   разомкнут, и наоборот. Следовательно, если переключателю Х поставлена в соответствие логическая переменная х, то переключателю   должна соответствовать переменная  .

    Всей  переключательной схеме также можно  поставить в соответствие логическую переменную, равную единице, если схема  проводит ток, и равную нулю — если не проводит. Эта переменная является функцией от переменных, соответствующих  всем переключателям схемы, и называется функцией проводимости.

    Найдем  функции проводимости F некоторых  переключательных схем:

a)   

Схема не содержит переключателей и проводит ток всегда, следовательно F=1; 
 

б)   

Схема содержит один постоянно разомкнутый контакт, следовательно F=0; 
 

в)   

Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, F(x) = x; 
 

г)   

Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут, следовательно, F(x) =  ; 
 

д)   

Схема проводит ток, когда оба переключателя замкнуты, следовательно, F(x) = x ^. y; 
 

е)   

Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, F(x)=x v y; 
 

ж)   

Схема состоит из двух параллельных ветвей и описывается  функцией  . 
 

    Задача  нахождения среди равносильных схем наиболее простых является очень  важной. Большой вклад в ее решение  внесли российские учёные Ю.И. Журавлев, С.В. Яблонский и др.

    При рассмотрении переключательных схем возникают  две основные задачи: синтез и анализ схемы.

    СИНТЕЗ  СХЕМЫ по заданным условиям ее работы сводится к следующим трём этапам:

1. составлению функции проводимости по таблице истинности, отражающей эти условия;
2. упрощению этой функции;
3. построению соответствующей схемы.

    АНАЛИЗ  СХЕМЫ сводится к

1. определению значений её функции проводимости при всех возможных наборах входящих в эту функцию переменных.
2. получению упрощённой формулы.