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

Зачем это нужно?

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

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

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

Минимизация логических функций при помощи карт Карно

Карта Карно - графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок. Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции. Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например:

Возможность поглощения следует из очевидных равенств

Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:

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

Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:

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

Для упрощения работы с булевыми функциями большого числа переменных был предложен следующий удобный приём. Куб, представляющий собой структуру термов, разворачивается на плоскость как показано на рисунке. Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы. При этом следует помнить, что порядок кодов термов в таблице (00 01 11 10) не соответствует порядку следования двоичных чисел, а клетки, находящиеся в крайних столбцах таблицы, соседствуют между собой.

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке. Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки. Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать.

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно - это таблица истинности составленная в 2-х мерном виде. Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности. После того как Карта заполнена, можно приступать к минимизации.

Если необходимо получить минимальную ДНФ, то в Карте рассматриваем только те клетки которые содержат единицы, если нужна КНФ, то рассматриваем те клетки которые содержат нули. Сама минимизация производится по следующим правилам (на примере ДНФ):

Далее берём первую область и смотрим какие переменные не меняются в пределах этой области, выписываем конъюнкцию этих переменных, если неменяющаяся переменная нулевая, проставляем над ней инверсию. Берём следующую область, выполняем то же самое что и для первой, и т. д. для всех областей. Конъюнкции областей объединяем дизъюнкцией.
Например(для Карт на 2-ве переменные):

Для КНФ всё то же самое, только рассматриваем клетки с нулями, не меняющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так для Карты Карно на рис.1 выражение в формате ДНФ будет иметь вид:

В формате КНФ:

Логика работы цифрового устройства описывается таблицей истинности, в которой показывается, какие логические уровни будут присутствовать на выходе цифровой схемы при заданных логических уровнях на входе этой схемы. Для того чтобы синтезировать схему с заданной логикой работы необходимо составить булево уравнение (в случаи если у схемы предполагается один выход) или систему уравнений (в случаи если выходов у схемы больше одного). Рассмотрим два способа составления уравнений из таблицы истинности: прямым и методом карт Карно.

Способ первый: составление уравнений из таблицы истинности прямым способом.

При составлении булевых уравнений прямым способом нужно учитывать, что получившиеся уравнения могут быть не минимально возможными.

Выделим алгоритм составления уравнения по таблице истинности:

• 1. Выделим те строки, в которых функция принимает истинное значение;
• 2. Составим для этих строк минтермы операндов;
• 3. Соединим минтермы при помощи операции дизъюнкции.

Рассмотрим пример.

Составим уравнение для устройства, имеющего один выход y, три входа x 0 , x 1 , x 2 . Логика работы устройства описана в таблицы 8.

Таблица 8 - Описание работы устройства

Составим функцию для строки три. В этой строке x 0 и x 2 принимают ложные значения, x 1 принимает истинное значение. Соединим эти операнды при помощи конъюнкции (элемент И):

Такая функции (принимающая истинное значения), в которую входит конъюнкция переменных или их отрицания называется минтермом.

Составим минтерм для строки пять:

Так как имеется два минтерма, соединим их при помощи дизъюнкции (элемент ИЛИ):

Что и будет уравнением устройства описанной таблицей истинности 8.

Выделим алгоритм составления системы уравнений по таблице истинности:

• 1. Определим количество выходов, следовательно, и количество уравнений в системе;
• 2. Для каждого из выходов составим уравнение:
• 2.1 Выделяем те строки, в которых функция принимает истинное значение;
• 2.2 Составлим для этих строк минтермы операндов;
• 2.3 Если минтермов больше одного, то соединим минтермы при помощи операции дизъюнкции.
• 3. Объединим полученные уравнения в систему.

Рассмотрим пример.

Пусть заданно устройство, логика работы которого описана в таблице 10. У устройства имеется два входа x 0 и x 1 , и два выхода y 1 , y 0 . Так как задано два выхода уравнения для каждого из выходов будут составляться отдельно. Составим систему уравнений, состоящую из двух уравнений.

Таблица 10 - Описание работы устройства

Выделим строки, в которых y 0 принимает истинные значения. y 0 принимает истинное значение только в одной строке, а именно в четвертой строке. Составим уравнение для y 0:

Выделим строки, в которых y 1 принимает истинные значения. Здесь имеется две строки: вторая и пятая. Для второй строки минтерм будет иметь вид. Для пятой. Объединим их с помощью операции ИЛИ, тем самым составив уравнение для y 1:

Остается составить систему уравнений, описывающую заданное устройство:

Способ второй: составление уравнений из таблицы истинности методом карт Карно.

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

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

Перед тем как привести примеры, отметим основные положения, которыми будем руководствоваться при объединении областей (групп):

• 1. Область, которая подвергается объединению, должна состоять из логических единиц, при этом объединению подлежат только прямоугольные области, содержащие число логических единиц 2 n (т.е. 2 клетки, 4 клетки и т.д.).
• 2. Клетки, находящиеся на границе карты, граничат между собой, и могут быть объединены.
• 3. Все единицы должны быть объединены в какую-либо область, причем количество областей должно быть минимальным.
• 4. Одна ячейка может быть включена в разные области.

Названные положения касаются только случая объединения областей, состоящих из логических единиц.

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

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

Пример 1. Составим уравнение содержащих два операнда (или их инверсию) по таблице истинности 11 посредствам карт Карно.

Таблица 11 - Карта Карно для двух операндов

Составим карту Карно, для этого преобразуем таблицу истинности к виду, показанному на рисунке 18.

Рис. 18.

Здесь, горизонтальная часть отводится операнду x 1 , которое принимает значение 0 и 1 (). Вертикальной части таблицы аналогично соответствует x 0 .

Выделим те строки таблицы истинности 11, где y принимает значение логической единицы: строки два и три. Заметим, что во второй строке x 0 и x 1 принимает значение 00 (), в третьей строке x 0 и x 1 принимает значение 10 ().

Проставим в карте Карно 18 на пересечениях x 0 x 1 единицы в тех местах, где и (рис. 19).

Рис. 19.

Выделим область согласно положениям объединения областей (Рис. 20).

Рис. 20.

Получена одна область, составим уравнение. Операнд меняет в области свое значение на инверсию. Неинвертированный операнд x 1 не входит в область. Единственный операнд, который не меняет своего значения в полученной области - . Тогда уравнение примет вид:

Заметим, что если составлять уравнение из таблицы 10 прямым способом, то получилось бы не минимизированное уравнение:

которое можно преобразовать к минимально возможной форме путем применения аксиом и свойств алгебры логики.

Пример 2. Составим уравнение содержащих три операнда (или их инверсию) по таблице истинности 12 посредствам карт Карно.

Таблица 12 - Карта Карно для трёх операндов

Составим карту Карно дл трех операндов (рис. 21).

Рис. 21.

Для трех операндов горизонтальная часть соответствует операндам x 1 x 2 , которые принимают значение 00, 01, 11, 10. Важно отметить, что порядок 00, 01, 11, 10 должен соблюдаться в точности, изменения его на другой порядок не допускается. Вертикальной части таблицы соответствует операнд x 0 , принимающей значение 1 и 0).

Заполним карту Карно. Аналогично предыдущему примеру: выделим строки в таблице истинности 12, где y принимает истинное значение (вторая, третья, четвертая, седьмая строки). Проставим единицы в те ячейки карты Карно, которые соответствуют значениям операндов в этих строках (рис. 22).

Рис. 22.

Выделим области согласно положениям объединения областей (Рис. 23).

Рис. 23.

Выделено две области. В первой области полностью находится операнды и, объединим их конъюнкцией. Во второй области не меняют своего значения операнды, объединим их в конъюнкцию. Так как есть две области, объединим конъюнкции областей операцией дизъюнкции, тем самым составив конечное уравнение:

Пример 4. Составим уравнение содержащих четыре операнда (или их инверсию) по таблице истинности 13 посредствам карт Карно.

Таблица 13 - Карта Карно для четырех операндов

Минимизация функций с использованием карты Карно

При минимизации функций f 1 и f 2 из табл. 3.2 нам приходилось искать наиболее активные способы преобразования исходных выражений. Например, далеко не очевидным было решение повторить терм на первом шаге минимизации функции f 2. - Для того чтобы как можно быстрее получить минимальное выражение, представляющее логическую функцию нескольких переменных, можно воспользоваться графическим представлением таблицы истинности, называемым картой Карно. Для функции трех переменных карта Карно представляет собой прямоугольник, составленный из восьми квадратов, расположенных в два ряда по четыре в каждом (рис. 3.14, а). Каждый квадрат соответствует конкретному набору значений входных переменных. Например, третий квадрат в верхнем ряду представляет значения (x 1 х 2 , х 3) = (1, 1, 0).

Поскольку в таблице истинности функции трех переменных содержится восемь строк, карта должна состоять из восьми квадратов. Значения внутри квадратов - это значения функции при соответствующих значениях переменных.

Главная идея карты Карно заключается в том, что расположенные рядом по горизонтали и по вертикали квадраты отличаются значениями только одной переменной. Если два смежных квадрата содержат единицы, это означает возможность алгебраического упрощения соответствующей пары термов. Например, на карте функции f 2 (рис. 3.14, а) единицы в двух крайних слева квадратах верхнего ряда соответствуют термам и х 2 . Эта пара термов упрощается следующим образом:

что мы и сделали в предыдущем разделе при минимизации алгебраического выражения для функции f 2 . Минимизированное произведение, соответствующее группе квадратов, - это произведение входных переменных, значения которых одинаковы для всех квадратов этой группы. Если значение входной переменной х i равно нулю для всех квадратов группы, тогда переменная х i входит в результирующее произведение. Квадраты с левого края карты считаются смежными с квадратами с ее правого края. Так, в карте функции f 2 имеется группа из четырех единиц, состоящая из крайнего слева столбца и крайнего справа столбца карты, Соответствующая группа термов упрощается до одного терма , содержащего единственную переменную, поскольку только переменная х 2 имеет одинаковые значения во всех квадратах группы.

Рис. 3.14. Минимизация функций с использованием карт Карно: карта для трех переменных (а); карта для четырех переменных (б);

Карты Карно могут использоваться и для минимизации функций более чем трех переменных. Карту для четырех переменных можно составить из двух карт для трех переменных. Два примера таких карт показаны на рис. 3.14, б, и под каждой из них приведено минимальное выражение для представляемой ею функции Если на карте для трех переменных квадраты можно группировать по два и по четыре, то на карте для четырех переменных их можно группировать еще и по восемь. Пример такой группировки показан на карте функции g 3 Обратите внимание, что четыре угловых квадрата можно объединить в одну группу, как на карте функции g 2 , где на их основе составлен терм . Как и в случае карты для трех переменных, терм, соответствующий группе квадратов, представляет собой произведение переменных, значения которых одинаковы для всех квадратов этой группы. Так, в группе из четырех квадратов в правом верхнем углу карты функции g 2 во всех квадратах х 1 = 1 и х 3 = 0, поэтому эту группу представляет терм х1 . Остальные две переменные, х 2 и x 4 имеют в квадратах этой группы разные значения. Карты Карно можно использовать и для функций пяти переменных. В этом случае для представления функции используются две карты для четырех переменных: одна из них соответствует значению 0 пятой переменной, а другая – ее значению 1.

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

В общем случае количество квадратов в группе должно быть равным 2 k , где k - целое число.

Теперь давайте рассмотрим процедуру получения с помощью карты Карно минимальной суммы произведений. Как видно на рис. 3.14, большей группе квадратов соответствует произведение меньшего числа переменных. Поэтому для получения минимального выражения нужно объединить все квадраты на карте, содержащие единицы, в как можно меньшее количество групп, выбирая наибольшие из них, так чтобы при этом охватить все единицы. Для примера рассмотрим карту функции g2 приведенную на рис. 3.14, б.

) по так называемым картам Карно.

Карты Карно — это другое графическое представление таблиц истинности. Структура таких карт для функции двух, трех и четырех переменных имеет вид:

Каждая клетка такой таблицы содержит значение логической функции x при фиксированном значении всех ее аргументов a 3 , a 2 , a 1 , a 0 т.е. Изображает одну из строчек таблицы истинности. Соответствующий аргумент считается истинным для данной клетки, если эта клетка входит в строки или столбцы, помеченные сбоку или снизу символом этого аргумента, в противном случае аргумент для данной клетки считается ложным. Сокращенную ДНФ записывают по прямоугольным группам смежных клеток карты содержащих единицу. Допустимое число клеток в группе равно 2 n , n=1,2,3,…

Правило записи сокращенной ДНФ аналогичны правилам записи ДСНФ и отличаются только тем, что в элементарных произведениях не указываются те аргументы, которые истинны лишь для половины клеток соответствующей группы.

Запишем, для примера, ДНФ в последующей карте Карно:

Сокращенная ДНФ для данного случая имеет вид:

При выделении прямоугольных групп клеток следует иметь в виду, что:

1. выделение групп часто неоднозначно, а, следовательно, неоднозначно и решение задачи синтеза;

2. группы должны быть как можно больше, а число групп как можно меньше;

3. группы могут пересекаться, т.е. иметь общие клетки

4. с точки зрения формирования прямоугольных групп, карты трех и четырех переменных следует считать трехмерными. Карму функции с тремя переменными следует рассматривать как цилиндр со склеенными правым и левым краями. Поэтому на плоском рисунке карты прямоугольные группы смежных клеток могут оказаться разорванными. Например:

В прямоугольной группе смежных клеток на нашем рисунке сокращенной ДНФ соответствует слагаемое.

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

По карте Карно можно записать также и сокращенную КНФ . Она записывается по прямоугольным группам смежных клеток содержащих нули. Прямоугольные группы выделяются также как и при записи ДНФ . Правило записи сокращенной КНФ аналогичны правилам записи КСНФ и отличаются только тем, что в элементарных суммах не учитываются те аргументы, которые истинны лишь для половины клеток соответствующей группы.

Метод карт Карно широко используется в инженерной практике при решении задач с числом аргументов не более четырех.

Назначение сервиса . Онлайн-калькулятор предназначен для построения таблицы истинности для логического выражения .
Таблица истинности – таблица содержащая все возможные комбинации входных переменных и соответствующее им значения на выходе.
Таблица истинности содержит 2 n строк, где n – число входных переменных, и n+m – столбцы, где m – выходные переменные.

Инструкция . При вводе с клавиатуры используйте следующие обозначения:

Логическое выражение :

Вывод промежуточных таблиц для таблицы истинности
Построение СКНФ
Построение СДНФ
Построение полинома Жегалкина
Построение карты Вейча-Карно
Минимизация булевой функции

Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис .

Правила ввода логической функции

1. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
3. Максимальное количество переменных равно 10 .

Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики - алгебры логики. В алгебре логики можно выделить три основные логические функции: "НЕ" (отрицание), "И" (конъюнкция), "ИЛИ" (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:
По алгебраической форме можно построить схему логического устройства, используя логические элементы.


Рисунок1- Схема логического устройства

Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможны х логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.

Операция НЕ - логическое отрицание (инверсия)

Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:

• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.

Для операции отрицания НЕ приняты следующие условные обозначения:
не А, Ā, not A, ¬А, !A
Результат операции отрицания НЕ определяется следующей таблицей истинности:

A	не А
0	1
1	0

Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.

Операция ИЛИ - логическое сложение (дизъюнкция, объединение)

Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
Применяемые обозначения: А или В, А V В, A or B, A||B.
Результат операции ИЛИ определяется следующей таблицей истинности:
Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В - ложны.

Операция И - логическое умножение (конъюнкция)

Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
Применяемые обозначения: А и В, А Λ В, A & B, A and B.
Результат операции И определяется следующей таблицей истинности:

A	B	А и B
0	0	0
0	1	0
1	0	0
1	1	1

Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.

Операция «ЕСЛИ-ТО» - логическое следование (импликация)

Эта операция связывает два простых логических выражения, из которых первое является условием, а второе - следствием из этого условия.
Применяемые обозначения:
если А, то В; А влечет В; if A then В; А→ В.
Таблица истинности:

A	B	А → B
0	0	1
0	1	1
1	0	0
1	1	1

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

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Применяемое обозначение: А ↔ В, А ~ В.
Таблица истинности:

A	B	А↔B
0	0	1
0	1	0
1	0	0
1	1	1

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

Применяемое обозначение: А XOR В, А ⊕ В.
Таблица истинности:

A	B	А⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.

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

• Действия в скобках
• Инверсия
• Конъюнкция (&)
• Дизъюнкция (V), Исключающее ИЛИ (XOR), сумма по модулю 2
• Импликация (→)
• Эквивалентность (↔)

Совершенная дизъюнктивная нормальная форма

Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами:

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все логические слагаемые формулы различны.
3. Ни одно логическое слагаемое не содержит переменную и её отрицание.
4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

СДНФ можно получить или с помощью таблиц истинности или с помощью равносильных преобразований.
Для каждой функции СДНФ и СКНФ определены единственным образом с точностью до перестановки.

Совершенная конъюнктивная нормальная форма

Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:

1. Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
2. Все элементарные дизъюнкции различны.
3. Каждая элементарная дизъюнкция содержит переменную один раз.
4. Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.