Электрическая схема, предназначенная для выполнения какой-либо логической операции с входными данными, называется логическим элементом. Входные данные представляются здесь в виде напряжений различных уровней, и результат логической операции на выходе - также получается в виде напряжения определенного уровня.
Операнды в данном случае подаются - на вход логического элемента поступают сигналы в форме напряжения высокого или низкого уровня, которые и служат по сути входными данными. Так, напряжение высокого уровня - это логическая единица 1 - обозначает истинное значение операнда, а напряжение низкого уровня 0 - значение ложное. 1 - ИСТИНА, 0 - ЛОЖЬ.
Логический элемент
- элемент, осуществляющий определенные логические зависимость между входными и выходными сигналами. Логические элементы обычно используются для построения логических схем вычислительных машин, дискретных схем автоматического контроля и управления. Для всех видов логических элементов, независимо от их физической природы, характерны дискретные значения входных и выходных сигналов.
Логические элементы имеют один или несколько входов и один или два (обычно инверсных друг другу) выхода. Значения «нулей» и «единиц» выходных сигналов логических элементов определяются логической функцией, которую выполняет элемент, и значениями «нулей» и «единиц» входных сигналов, играющих роль независимых переменных. Существуют элементарные логические функции, из которых можно составить любую сложную логическую функцию.
В зависимости от устройства схемы элемента, от ее электрических параметров, логические уровни (высокие и низкие уровни напряжения) входа и выхода имеют одинаковые значения для высокого и низкого (истинного и ложного) состояний.
Традиционно логические элементы выпускаются в виде специальных радиодеталей - интегральных микросхем. Логические операции, такие как конъюнкция, дизъюнкция, отрицание и сложение по модулю (И, ИЛИ, НЕ, исключающее ИЛИ) - являются основными операциями, выполняемыми на логических элементах основных типов. Далее рассмотрим каждый из этих типов логических элементов более внимательно.
Логический элемент «И» - конъюнкция, логическое умножение, AND
«И» - логический элемент, выполняющий над входными данными операцию конъюнкции или логического умножения. Данный элемент может иметь от 2 до 8 (наиболее распространены в производстве элементы «И» с 2, 3, 4 и 8 входами) входов и один выход.
Условные обозначения логических элементов «И» с разным количеством входов приведены на рисунке. В тексте логический элемент «И» с тем или иным числом входов обозначается как «2И», «4И» и т. д. - элемент «И» с двумя входами, с четырьмя входами и т. д.
Таблица истинности для элемента 2И показывает, что на выходе элемента будет логическая единица лишь в том случае, если логические единицы будут одновременно на первом входе И на втором входе. В остальных трех возможных случаях на выходе будет ноль.
На западных схемах значок элемента «И» имеет прямую черту на входе и закругление на выходе. На отечественных схемах - прямоугольник с символом «&».
Логический элемент «ИЛИ» - дизъюнкция, логическое сложение, OR
«ИЛИ» - логический элемент, выполняющий над входными данными операцию дизъюнкции или логического сложения. Он так же как и элемент «И» выпускается с двумя, тремя, четырьмя и т. д. входами и с одним выходом. Условные обозначения логических элементов «ИЛИ» с различным количеством входов показаны на рисунке. Обозначаются данные элементы так: 2ИЛИ, 3ИЛИ, 4ИЛИ и т. д.
Таблица истинности для элемента «2ИЛИ» показывает, что для появления на выходе логической единицы, достаточно чтобы логическая единица была на первом входе ИЛИ на втором входе. Если логические единицы будут сразу на двух входах, на выходе также будет единица.
На западных схемах значок элемента «ИЛИ» имеет закругление на входе и закругление с заострением на выходе. На отечественных схемах - прямоугольник с символом «1».
Логический элемент «НЕ» - отрицание, инвертор, NOT
«НЕ» - логический элемент, выполняющий над входными данными операцию логического отрицания. Данный элемент, имеющий один выход и только один вход, называют еще инвертором, поскольку он на самом деле инвертирует (обращает) входной сигнал. На рисунке приведено условное обозначение логического элемента «НЕ».
Таблица истинности для инвертора показывает, что высокий потенциал на входе даёт низкий потенциал на выходе и наоборот.
На западных схемах значок элемента «НЕ» имеет форму треугольника с кружочком на выходе. На отечественных схемах - прямоугольник с символом «1», с кружком на выходе.
Логический элемент «И-НЕ» - конъюнкция (логическое умножение) с отрицанием, NAND
«И-НЕ» - логический элемент, выполняющий над входными данными операцию логического сложения, и затем операцию логического отрицания, результат подается на выход. Другими словами, это в принципе элемент «И», дополненный элементом «НЕ». На рисунке приведено условное обозначение логического элемента «2И-НЕ».
Таблица истинности для элемента «И-НЕ» противоположна таблице для элемента «И». Вместо трех нулей и единицы - три единицы и ноль. Элемент «И-НЕ» называют еще «элемент Шеффера» в честь математика Генри Мориса Шеффера, впервые отметившего значимость этой в 1913 году. Обозначается как «И», только с кружочком на выходе.
Логический элемент «ИЛИ-НЕ» - дизъюнкция (логическое сложение) с отрицанием, NOR
«ИЛИ-НЕ» - логический элемент, выполняющий над входными данными операцию логического сложения, и затем операцию логического отрицания, результат подается на выход. Иначе говоря, это элемент «ИЛИ», дополненный элементом «НЕ» - инвертором. На рисунке приведено условное обозначение логического элемента «2ИЛИ-НЕ».
Таблица истинности для элемента «ИЛИ-НЕ» противоположна таблице для элемента «ИЛИ». Высокий потенциал на выходе получается лишь в одном случае - на оба входа подаются одновременно низкие потенциалы. Обозначается как «ИЛИ», только с кружочком на выходе, обозначающим инверсию.
Логический элемент «исключающее ИЛИ» - сложение по модулю 2, XOR
«исключающее ИЛИ» - логический элемент, выполняющий над входными данными операцию логического сложения по модулю 2, имеет два входа и один выход. Часто данные элементы применяют в схемах контроля. На рисунке приведено условное обозначение данного элемента.
Изображение в западных схемах - как у «ИЛИ» с дополнительной изогнутой полоской на стороне входа, в отечественной - как «ИЛИ», только вместо «1» будет написано «=1».
Этот логический элемент еще называют «неравнозначность». Высокий уровень напряжения будет на выходе лишь тогда, когда сигналы на входе не равны (на одном единица, на другом ноль или на одном ноль, а на другом единица) если даже на входе будут одновременно две единицы, на выходе будет ноль - в этом отличие от «ИЛИ». Данные элементы логики широко применяются в сумматорах.
Таблица истинности - это таблица, которая описывает логическую функцию. Логическая функция здесь - это функция, у которой значения переменных и значение самой функции выражают истинность. Например, они принимают значения «истина» либо «ложь» (true либо false, 1 либо 0).
Таблицы истинности применяются для определения значения какого-либо высказывания для всех возможных случаев значений истинности высказываний, которые его составляют. Количество всех существующих комбинаций в таблице находится по формуле N=2*n; где N - общее количество возможных комбинаций, n - число входных переменных. Таблицы истинности нередко используются в цифровой технике и булевой алгебре, чтобы описать работу логических схем.
Таблицы истинности для основных функций
Примеры : конъюнкция - 1&0=0, импликация - 1→0=0.
Порядок выполнения логических операций
Инверсия; Конъюнкция; Дизъюнкция; Импликация; Эквиваленция; Штрих Шеффера; Стрелка Пирса.
Последовательность построения (составления) таблицы истинности:
- Определить количество N используемых переменных в логическом выражении.
- Вычислить количество всевозможных наборов значений переменных M = 2 N , равное количеству строк в таблице.
- Подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество логических операций.
- Озаглавить столбцы таблицы названиями переменных и названиями логических операций.
- Заполнить столбцы логических переменных наборами значений, например, от 0000 до 1111 с шагом 0001 в случае для четырех переменных.
- Заполнить таблицу истинности по столбцам со значениями промежуточных операций слева направо.
- Заполнить окончательный столбец значений для функции F.
Таким образом, можно составить (построить) таблицу истинности самостоятельно.
Составить таблицу истинности онлайн
Заполните поле ввода и нажмите OK. T - истина, F - ложь. Рекомендуем добавить страницу в закладки или сохранить в социальной сети.
Обозначения
- Множества или выражения большими буквами латинского алфавита: A, B, C, D...
- A" - штрих - дополнения множеств
- && - конъюнкция ("и")
- || - дизъюнкция ("или")
- ! - отрицание (например, !A)
- \cap - пересечение множеств \cap
- \cup - объединение множеств (сложение) \cup
- A&!B - разность множеств A∖B=A-B
- A=>B - импликация "Если..., то"
- AB - эквивалентность
Решение логических выражений принято записывать в виде таблиц истинности – таблиц, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных.
При составлении таблицы истинности для логического выражения необходимо учитывать порядок выполнения логических операций , а именно:
- действия в скобках,
- инверсия (отрицание ),
- & (конъюнкция ),
- v (дизъюнкция ),
- => (импликация ),
- <=> (эквивалентность ).
Алгоритм составления таблицы истинности :
1. Выяснить количество строк в таблице (вычисляется как 2 n , где n – количество переменных + строка заголовков столбцов).
2. Выяснить количество столбцов (вычисляется как количество переменных + количество логических операций).
3. Установить последовательность выполнения логических операций.
4. Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных.
5. Заполнить таблицу истинности по столбцам.
6. Записать ответ.
|
Пример 6 Построим таблицу истинности для выражения F =(Av B )&(¬ A v ¬ B ) .1. Количество строк=2 2 (2 переменных+строка заголовков столбцов)=5. 2. Количество столбцов=2 логические переменные (А, В)+ 5 логических операций (v ,&, ¬ , v , ¬ ) = 7. 3. Расставим порядок выполнения операций: 1 5 2 43 (A v B ) & (¬ A v ¬ B ) 4-5. Построим таблицу и заполним ее по столбцам:
6. Ответ: F =0, при A= B=0 и A= B=1 Пример 7 Построим таблицу истинности для логического выражения F = X v Y & ¬ Z . 1. Количество строк=2 3 +1=(3 переменных+строка заголовков столбцов)=9. 2. Количество столбцов=3 логические переменные+3 логических операций = 6. 3. Укажем порядок действий: 3 2 1 X v Y & ¬ Z 4-5. Построи м таблицу и заполним ее по столбцам:
6. Ответ: F =0, при X= Y= Z= 0; при X= Y=0 и Z= 1. |
Упражнение 8
Постройте таблицы истинности для следующих логических выражений:
1. F =(Av B )&(¬ A& ¬ B).
2. F = X&¬ Yv Z.
Проверьте себя (эталон ответов)
Обратите внимание!
Наборы входных переменных, во избежание ошибок, рекомендуется перечислять следующим образом:
А) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю единицами;
Б) разделить колонкузначенийвторой переменной на четыре части и заполнить каждую четверть чередующимися группами нулей и единиц, начиная с группы нулей;
В) продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами нулей или единиц до тех пор, пока группы нулей и единиц не будут состоять из одного символа.
Тавтология - тождественно истинная формула истина " ("1
Противоречие - тождественно ложная формула , или формула принимающая значение "ложь " ("0 ") при любых входящих в нее значениях переменных.
Равносильные формулы - две формулы А и В принимающие одинаковые значения, при одинаковых наборах значений входящих в них переменных. Равносильность двух формул алгебры логики обозначается символом .
Продолжительность урока: 45 мин
Тип урока: комбинированный:
- проверка знаний – устная работа;
- новый материал – лекция;
- закрепление – практические упражнения;
- проверка знаний – задания для самостоятельной работы.
Цели урока:
- дать понятие таблицы истинности;
- закрепление материала предыдущего урока “Алгебра высказываний”;
- использование информационных технологий;
- привитие навыка самостоятельного поиска нового материала;
- развитие любознательности, инициативы;
- воспитание информационной культуры.
План урока:
- Организационный момент (2 мин).
- Повторение материала предыдущего урока (устный опрос) (4 мин).
- Объяснение нового материала (12 мин).
- Закрепление
- разбор примера (5 мин);
- практические упражнения (10 мин);
- задания для самостоятельной работы (10 мин).
Оборудование и программный материал:
- белая доска;
- мультимедийный проектор;
- компьютеры;
- редактор презентаций MS PowerPoint 2003;
- раздаточный справочный материал “Таблицы истинности”;
- демонстрация презентации “Таблицы истинности”.
Ход урока
I. Организационный момент
Мы продолжаем изучение темы “Основы логики”. На предыдущих уроках мы увидели, что логика достаточно крепко связана с нашей повседневной жизнью, а также увидели, что почти любое высказывание можно записать в виде формулы.
II. Повторение материала предыдущего урока
Давайте вспомним основные определения и понятия:
| Вопрос | Ответ |
| 1. Какое предложение является высказыванием? | Повествовательное предложение, в котором что-либо утверждается или отрицается |
| 2. На какие виды делятся высказывания по своей структуре? | Простые и сложные |
| 3. Истинность каких высказываний является договорной? | Простых |
| 4. Истинность каких высказываний вычисляется? | Сложных |
| 5. Как обозначаются простые высказывания в алгебре высказываний? | Логическими переменными |
| 6. Как обозначается истинность таких высказываний? | 1 и 0 |
| 7. Что связывает переменные в формулах алгебры высказываний? | Логические операции |
| 8. Перечислите их. | Инверсия (отрицание) Конъюнкция (умножение) Дизъюнкция (сложение) Импликация (следование) Эквиваленция (равносильность) |
| 9. Определите, соответствует ли формула сложному высказыванию. Назовите простые высказывания. Определите причину несоответствия. (Задание на экране) | Нет, неправильно поставлен знак |
| 10. Определите, соответствует ли формула сложному высказыванию. Назовите простые высказывания. Определите причину несоответствия. (Задание на экране) | Да |
III. Объяснение нового материала
Последние два примера относятся к сложным высказываниям. Как же определить истинность сложных высказываний?
Мы говорили, что она вычисляется. Для этого в логике существуют таблицы для вычисления истинности составных (сложных) высказываний. Они называются таблицами истинности.
Итак, тема урока ТАБЛИЦЫ ИСТИННОСТИ.
3.1) Определение. Таблица истинности – это таблица, показывающая истинность сложного высказывания при всех возможных значениях входящих переменных (Рисунок 1).
3.2) Разберем подробнее каждую логическую операцию в соответствии с ее определением:
1. Инверсия (отрицание) – это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.
Эта операция относится только к одной переменной, поэтому для нее отведено только две строки, т.к. одна переменная может иметь одно из двух значений: 0 или 1.
2. Конъюнкция (умножение)– это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.
Легко увидеть, что данная таблица действительно похожа на таблицу умножения.
3. Дизъюнкция (сложение) – это логическая операция, которая каждым двум простым высказываниям ставит в соответствие составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны.
Можно убедиться, что таблица похожа на таблицу сложения кроме последнего действия. В двоичной системе счисления 1 + 1 = 10, в десятичной – 1 + 1 = 2. В логике значения переменной 2 невозможно, рассмотрим 10 с точки зрения логики: 1 – истинно, 0 – ложно, т.о. 10 – истинно и ложно одновременно, чего быть не может, поэтому последнее действие строго опирается на определение.
4. Импликация (следование) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие истинное, а следствие ложно.
5. Эквиваленция (равносильность) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или ложны.
Последние две операции были разобраны нами на предыдущем уроке.
3.3) Разберем алгоритм составления таблицы истинности для сложного высказывания:
3.4) Рассмотрим пример составления таблицы истинности для сложного высказывания:
Пример. Построить таблицу истинности для формулы: А U В -> ¬А U С.
Решение (Рисунок 2)
Из примера видно, что таблицей истинности является не все решение, а только последнее действие (столбец, выделенный красным цветом).
IV. Закрепление.
Для закрепления материала вам предлагается решить самостоятельно примеры под буквами а, б, в, дополнительно г–ж (Рисунок 3).
V. Домашнее задание, обобщение материала.
Домашнее задание дано вам также на экране монитора (Рисунок 4)
Обобщение материала: сегодня на уроке мы научились определять истинность составных высказываний, но больше с математической точки зрения, так как вам были даны не сами высказывания, а формулы, отображающие их. На следующих уроках мы закрепим эти умения и постараемся их применить к решению логических задач.
Назначение сервиса . Онлайн-калькулятор предназначен для построения таблицы истинности для логического выражения .Таблица истинности – таблица содержащая все возможные комбинации входных переменных и соответствующее им значения на выходе.
Таблица истинности содержит 2 n строк, где n – число входных переменных, и n+m – столбцы, где m – выходные переменные.
Инструкция
. При вводе с клавиатуры используйте следующие обозначения:
Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис .
Правила ввода логической функции
- Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
- Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
- Максимальное количество переменных равно 10 .
Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики - алгебры логики. В алгебре логики можно выделить три основные логические функции: "НЕ" (отрицание), "И" (конъюнкция), "ИЛИ" (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:
- словесное описание – это форма, которая используется на начальном этапе проектирования имеет условное представление.
- описание функции алгебры логики в виде таблицы истинности.
- описание функции алгебры логики в виде алгебраического выражения: используется две алгебраические формы ФАЛ:
а) ДНФ – дизъюнктивная нормальная форма – это логическая сумма элементарных логических произведений. ДНФ получается из таблицы истинности по следующему алгоритму или правилу:
1) в таблице выбираются те строки переменных для которых функция на выходе =1 .
2) для каждой строки переменных записывается логическое произведение; причём переменные =0 записываются с инверсией.
3) полученное произведение логически суммируется.
Fднф= X 1 *Х 2 *Х 3 ∨ Х 1 x 2 Х 3 ∨ Х 1 Х 2 x 3 ∨ Х 1 Х 2 Х 3
ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде.
б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
КНФ может быть получена из таблицы истинности по следующему алгоритму:
1) выбираем наборы переменных для которых функция на выходе =0
2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
3) логически перемножаются полученные суммы.
Fскнф=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
КНФ называется совершенной , если все переменные имеют одинаковый ранг.
Рисунок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
- Импликация (→)
- Эквивалентность (↔)
Совершенная дизъюнктивная нормальная форма
Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами:- Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
- Все логические слагаемые формулы различны.
- Ни одно логическое слагаемое не содержит переменную и её отрицание.
- Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.
Для каждой функции СДНФ и СКНФ определены единственным образом с точностью до перестановки.
Совершенная конъюнктивная нормальная форма
Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:- Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x 1 ,x 2 ,...x n).
- Все элементарные дизъюнкции различны.
- Каждая элементарная дизъюнкция содержит переменную один раз.
- Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.