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

Определение. Формулу называют элементарной конъюнкцией, если она образованна конъюнкцией некоторого числа переменных или их отрицаний.

Примеры: y, y, х₁ ∧ х₂ ∧ х₃ ∧ х₄

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

ДНФ записывается в следующей форме: F₁ ∨ F₂ ∨ ... ∨ F_n, где F_i - элементарная конъюнкция

Примеры: х₁ ∧ х₂ ∨ х₁ ∧ х₂ ∨ х₁ ∧ х₂ ∧ х₃, y₁ ∨ y₁ ∧ y₂ ∨ y₂

Определение. Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой конъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные конъюнкции в такой ДНФ попарно различны.

Пример: ( х₁ ∧ х₂ ∧ х₃) ∨ (х₁ ∧ х₂ ∧ х₃) ∨ (х₁ ∧ х₂ ∧ х₃)

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

Определение. Формулу называют элементарной дизъюнкцией, если она образована дизъюнкцией некоторого числа переменных или их отрицаний.

Примеры: х₃, х₁ ∨ х₂, х₁ ∨ х₂ ∨ х₃

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

КНФ записывается в следующей форме: F₁ ∧ F₂ ∧ ... ∧ F_n, где F_i - элементарная дизъюнкция

Примеры: (х₁ ∨ х₂) ∧ х₃, (х₁ ∨ х₂) ∧ ( х₁ ∨ х₂ ∨ х₃) ∧ ( х₁ ∨ х₂ ∨ х₃)

Определение. Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х₁, х₂, …, х_k, причем на i-м месте этой дизъюнкции стоит либо переменная х_i, либо ее отрицание;
2) все элементарные дизъюнкции в такой КНФ попарно различны.

Пример: (х₁ ∨ х₂ ∨ х₃) ∧ ( х₁ ∨ х₂ ∨ х₃)

Заметим, что любую логическую функцию, не равную тождественно 0 или 1, можно представить в виде СДНФ или СКНФ.

Алгоритм построения СДНФ по таблице истинности

1. Выбрать все строки таблицы, в которых значение функции равно единице.

2. Для каждой такой строки записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — ее отрицание.

3. Все полученные конъюнкции связываем операциями дизъюнкции.

Алгоритм построения СКНФ по таблице истинности

1. Выбрать все строки таблицы, в которых значение функции равно нулю.

2. Для каждой такой строки записать дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 0, то в конъюнкцию включаем саму переменную, в противном случае — ее отрицание.

3. Все полученные дизъюнкции связываем операциями конъюнкции.

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

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

x	y	z	F (x, y, z)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Т.к. на большинстве строк таблицы истинности значение функции равно 1, то построим СКНФ. В результате получим следующую логическую формулу:
F = ( x ∨ y ∨ z) ∧ ( x ∨ y ∨ z)

Проверим полученную формулу. Для этого построим таблицу истинности функции.

x	y	z	x	x ∨ y ∨ z	z	x ∨ y ∨ z	F (x, y, z)
0	0	0	1	1	1	1	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	1	1
0	1	1	1	1	0	1	1
1	0	0	0	0	1	1	0
1	0	1	0	1	0	0	0
1	1	0	0	1	1	1	1
1	1	1	0	1	0	1	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. получению упрощённой формулы.

__________________________________________________________________________________________________________________________________ ЛОГИЧЕСКИЕ СХЕМЫ

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

В цифровой схемотехнике цифровой сигнал - это сигнал, который может принимать два значения, рассматриваемые как логическая "1" и логический "0".

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

Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах (для увеличения можно нажать на рисунок левой кнопкой мыши).

⇐ Предыдущая12345Следующая ⇒

Поделиться: