Главная > Документ


Отрицание

= 1 (1.1)

= 0 (1.2)

= x (1.3)

Конъюнкция

0 & 0 = 0 (1.4)

0 & 1 = 0 (1.5)

1 & 1 = 1 (1.6)

0 & x = 0 (1.7)

1 & x = x (1.8)

x & ¯x = 0 (1.9)

x & x = x (1.10)

x & x &...& x = x (1.11)

x & y = y & x (1.12)

x & y & z = (x & y) & z = x & (y & z) (1.13)

Дизъюнкция

00 = 0 (1.14)

01 = 1 (1.15)

11 = 1 (1.16)

0x = x (1.17)

1x = 1 (1.18)

x¯x = 1 (1.19)

xx = x (1.20)

xx...x = x (1.21)

xy = yx (1.22)

xyz = (xy) z = x (yz) (1.23)

Штрих Шеффера

0/0 = 1 (1.24)

0/1 = 1 (1.25)

1/1 = 0 (1.26)

0/x = 1 (1.27)

1/x = ¯x (1.28)

x/x = ¯x (1.29)

xx = 1 (1.30)

x/y = y/x (1.31)

x/(y/z)  (x/y)/z (1.32)

Стрелка Пирса

00=1 (1.33)

01=0 (1.34)

11=0 (1.35)

0xx (1.36)

1x=0 (1.37)

xxx (1.38)

x  ¯x = 0 (1.39)

xy=yx (1.40)

x(yz)(xy)z (1.41)

Правила де Моргана

= (1.42)

= & &…& (1.43)

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


Например, F2(a,b,c) = ¯a & b & ¯c .

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

f(x1,x2,…,xn) = x1α11x2α12xnα1nVx1α21x2α22xnα2nV…Vx1αm1x2αm2xnαmn=

= Vix1α1x2α2xnαn,

где Vi – символ обобщенной дизъюнкции по всем минтермам данной функции:

Иногда для обозначения обобщенной дизъюнкции используется символ ∑i.

Иными словами, совершенной дизъюнктивной нормальной формой некоторой логической функции называется дизъюнкция всех конституэнт единицы этой ФАЛ. Любую ФАЛ, кроме константы ";ноль";, можно представить в виде СДНФ. Любая ФАЛ имеет единственную СДНФ с точностью до перестановки ее членов.

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


Например, Ф5(a,b,c) = ¯a v b v ¯c ..

Рангом терма называется количество переменных, составляющих данный терм.

Совершенная конъюнктивная нормальная форма (СКНФ) – ФАЛ, заданная в виде:

f(x1,x2,…,xn) = (x1α11 v x2α12 v … xnα1n) Λ (x1α21 v x2α22 v … v xnα2n) Λ …

…Λ (x1αm1 v x2αm2 v … v xnαmn) = Λi (x1α1 Λ x2α2 Λ … Λ xnαn),

где Λi – символ обобщенной конъюнкции по всем макстермам данной функции. Иногда для обозначения обобщенной конъюнкции используется символ ∏i или &i.

Иными словами, совершенной конъюнктивной нормальной формой некоторой логической функ­ции называется конъюнкция всех конституэнт нуля этой ФАЛ. Любую ФАЛ, кроме константы ";единица";, можно представить в виде СКНФ. Любая ФАЛ имеет един­ст­венную СКНФ с точностью до перестановки ее членов.

Конъюнкция нескольких различных переменных, взятых с отрицаниями или без них, называется элементарной конъюнкцией.

Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ). Например, функция ab v ¯ac v v c не является ДНФ, так как член не яв­ляет­ся элементарной конъюнкцией, а функция ab v ¯ac v abc является дизъюнктивной нормальной формой некоторой ФАЛ.

Импликанта функции – некоторая логическая функция, об­ра­ща­е­мая в ноль, по крайней мере, на тех же наборах переменных, на которых сама функция также равна нулю.

Примерами импликант могут служить любой минтерм функции или группа минтермов, объединенная знаком дизъюнкции.

Собственной частью элементарной конъюнкции называют терм, полученный путем исключения из элементарной конъюнкции одного или не­скольких сомножителей. Например, элементарная конъюнкция ac имеет следующие собственные части a, ac, c, a, , c.

Первичная импликанта функции – импликанта типа элементарной конъюнкции некоторых переменных, никакая собственная часть которой уже не является импликантой.

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

Дизъюнктивная нормальная форма ФАЛ называется минимальной (МДНФ), если количество букв, которое она содержит, будет не больше, чем в любой другой дизъюнктивной нормальной фор­ме той же ФАЛ. Некоторые ФАЛ имееют несколько МДНФ.

Тупиковой дизъюнктивной нормальной формой называется дизъюнкция первичных импликант, ни одна из которых не является лишней. ФАЛ может иметь несколько тупиковых форм. Минимальные формы также являются тупиковыми. Поэтому процесс отыскания минимальных форм сводится к получению всех тупиковых форм и выбору из них форм с минимальным количеством букв.

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

Конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ). Пример конъюнктивной нормальной формы: (a v ) & ( ¯a v c) & (a v b v c)

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

Определение понятий, относящихся к конъюнктивным нор­мальным формам, аналогичны определениям, относящимся к дизъ­­юнктивным формам, в предположении, что термин ";импликанта"; заменяется на термин ";имплицента";.

Базис – набор функций алгебры логики, с помощью которых любая ФАЛ может быть представлена суперпозицией функций, составляющих базис.

2. Представление функций алгебры логики

Основная форма представления функций алгебры логики - таблица истинности (ТИ), которая определяет значение функции на всех наборах переменных.

Таблицами истинности для функций одной и двух переменных являются таблицы 1.1 и 1.2 соответственно.

Помимо таблицы истинности, возможны и другие виды представления ФАЛ, наиболее распрост­раненными из которых являются совершенная дизъюнктивная нормальная форма, описывающая все наборы переменных, на которых функция принимает значение, равное 1, и совершенная конъюнктивная нормальная форма, описывающая все наборы переменных, на которых функция принимает значение, равное 0.

Рассмотрим способы перехода от одного вида представления ФАЛ к другому.

Пример 2.1

Пусть ФАЛ задана в виде таблицы истинности (2.1).

Таблица 2.1

Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

1

0

0

1

0

2

0

1

0

0

3

0

1

1

1

4

1

0

0

1

5

1

0

1

1

6

1

1

0

0

7

1

1

1

1

Получить СДНФ и СКНФ этой функции.
Решение

Получение СДНФ.

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

f(x,y,z)СДНФ = (0,3,4,5,7)

Примечания:

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

Получение развернутой записи СДНФ включает следующие этапы.

Этап 1.

Записать дизъюнкцию k конъюнктивных термов, содержащих все переменные, от которых зависит функция, где k - количество наборов, на которых функция принимает значение, равное 1, то есть количество наборов, перечисленное в сокращенной записи СДНФ:

f(x,y,z) =xyz V xyz V xyz V xyz V xyz

Этап 2.

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

f(x,y,z) =xyz V xyz V xyz V xyz V xyz

000 011 100 101 111

Этап 3.

Расставить знаки отрицания над теми переменными, которым в двоичном эквиваленте соответствует 0:

f(x,y,z)СДНФ =xyz V xyz V xyz V xyz V xyz

0 0 0 0 1 1 1 0 0 1 0 1 1 1 1

Полученная запись представляет собой совершенную дизъюнктивную нормальную форму для функции, заданной таблицей истинности 2.1.

Получение СКНФ.

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

f(x,y,z)СКНФ= (1,2,6)

Примечания:

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

Получение развернутой записи СДНФ включает следующие этапы.

Этап 1.

Записать конъюнкцию m дизъюнктивных термов, содержащих все переменные, от которых зависит функция, где m - количество наборов, на которых функция принимает значение, равное 0, то есть количество наборов, перечисленное в сокращенной записи СКНФ:

f(x,y,z) = (xVyVz) & (xVyVz) & (xVyVz)

Этап 2.

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

f(x,y,z) = (xVyVz) & (xVyVz) & (xVyVz)

0 0 1 0 1 0 1 1 0

Этап 3.

Расставить знаки отрицания над теми переменными, которым в двоичном эквиваленте соответствует 1:

f(x,y,z)СКНФ = (x V y Vz) & (x Vy V z) & (x Vy V z)

0 0 1 0 1 0 1 1 0

Полученная запись представляет собой совершенную конъюнктивную нормальную форму для функции, заданной таблицей истинности 2.1.

Пример 2.2

Пусть ФАЛ задана сокращенной записью СДНФ:

f(x,y,z)СДНФ=(0,1,2,5,7)

Представить таблицу истинности, а также полную и сокращенную записи СКНФ этой функции.

Решение
Получение таблицы истинности

Этап 1.

Подготовить ТИ для логической функции трех переменных

Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

0

0

1

2

0

1

0

3

0

1

1

4

1

0

0

5

1

0

1

6

1

1

0

7

1

1

1

Этап 2.

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

Номер набора

x

y

z

f(x,y,z)

0

0

0

0

1

1

0

0

1

1

2

0

1

0

1

3

0

1

1

4

1

0

0

5

1

0

1

1

6

1

1

0

7

1

1

1

1



Скачать документ

Похожие документы:

  1. Библиографический указатель из фонда научной библиотеки

    Библиографический указатель
    ... -технических работ. МИФИ - городу Москве:Каталог.-М.,2001.-Б.п. 195. Московский государственный инженерно-физический ... .-26с. 4553. Гуров В.В. Синтезкомбинационныхсхем в примерах и решениях: Учеб.пособие/Гуров В.В.-М.:МИФИ,2001.-56с. 4554. Гусев ...
  2. Москва 2011 1 Цели и задачи дисциплины (3)

    Рабочая программа
    ... коммуникационные технологии Москва 2011 1. ... схемотехнических решений и ... и синтезасхем ЭВМ. Анализ комбинационныхсхем. Синтезкомбинационныхсхем: мультиплексор ... СПб.: БХВ-Петербург, 2001. 2. Пухальский Г.И., Новосельцева ... также примеры оценочных ...
  3. Программа обучения студентов ( syllabus ) (3)

    Программа обучения студентов
    ... домашних заданий, самостоятельное решение задач), итоги индивидуальных ... А.В. и др. «Информатика». – Москва.: ACADEMA, 1999 г. Информатика/ Под ... ДИАЛОГ-МИФИ,1993 Гуров В.В. Синтезкомбинационныхсхем в примерах М.: МИФИ, 2001 Гуров В.В., Ленский О.Д., ...
  4. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...
  5. РУССКАЯ ВЕРОЯТНОСТНАЯ ЛОГИКА (2)

    Документ
    ... -ЭЛЕКТРОНЩИКА Москва 2008 ... Русская механика» А.Ф.Черняева (М.:2001 – 592с.) и « ... 1.4. СинтезкомбинационныхсхемСинтезкомбинационныхсхем можно проиллюстрировать решением простой ... Пример 1. «Энциклопедия - Россия-Он-Лайн» излагает примеррешения ...

Другие похожие документы..