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

Формы логических функций

Элементарные логические функции

Понятие логической функции

Понятие высказывания

Понятие алгебры логики

Основные определения

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

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Её создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Алгебра логики применяется:

1) для упрощения сложных логических формул и доказательств тождеств;

2) при решении логических задач;

3) в контактных схемах;

4) при доказательствах теорем;

5) в базах данных при составлении запросов.

Под высказыванием (суждением) понимают повествовательное предложение, относительно которого можно сказать, истинно или ложно.

Логическое высказывание - утверждение, которому всегда можно поставить в соответствие одно из двух логических значений ложь (0, ложно, false) или истина (1, истинно, true). Логическое высказывание принято обозначать заглавными латинскими буквами.

Логическая переменная – это такая переменная, которая может принимать одно из двух возможных значений: 0 или 1.

Логическая функция – это закон соответствия между логическими переменными.

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

К основным относятся следующие элементарные логические функции: отрицание, логическое умножение, логическое сложение, эквиваленция, импликация, исключающее ИЛИ.

Нормальные формы

· все элементарные дизъюнкции и конъюнкции имеют одинаковый ранг – число переменных

· в элементарные дизъюнкции и конъюнкции входят все те переменные или их отрицания, от которых зависит функция

Правило записи:

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

Пример:

Функция F(x1,x2,x3) равна единице на наборах 3,5,6,7 (011,101,110,111). Записать функцию с использованием СДНФ

 

x1	x2	x3	F

Дата добавления: 2014-01-07