Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности,дизъюнкция


Добавил:DMT
Дата создания:22 июня 2008, 20:36
Дата обновления:22 июня 2008, 21:25
Просмотров:34356 последний позавчера, 17:01
Комментариев: 1

БУЛЕВЫ ФУНКЦИИ

1. Функции и константы алгебры логики

          Пусть I = {0, 1} – множество, состоящее из двух элементов: 0 (ложь) и 1 (истина). Функцией алгебры логики или булевой функцией f : In ® I называется произвольная функция f(x1, x2, …, xn) от n аргументов, принимающая значения в I. Будем предполагать, что функции от n переменных определены для всех натуральных чисел n і 0, причем функциями от 0 переменных являются константы 0 и 1.

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

 

2. Несущественные переменные и равенство функций

         Для того чтобы производить операции над функциями, например, из функций f(x1, x2) = x1 + x2 - x1x2, g(x1) = 1 - x1, получить функцию f(x1, x2) Ч g(x1), удобно предполагать, что области определения функций f и g совпадают. С этой целью вводиться понятие несущественной переменной. В данном примере функция g(x) рассматривается как функция от x1 и x2, для которой переменная x2 – несущественная.

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности


          Определение. Функция f(x1, …, xn) зависит существенным образом от аргумента xi , если существуют такие значения аргументов a1, …, ai-1, ai+1, …, an, что f(a1, …, ai-1, 0, ai+1, …, an) f(a1, …, ai-1, 1, ai+1, …, an). В противном случае переменная xi называется несущественной или фиктивной. Две булевы функции называются равными, если одна из другой получается введением или удалением несущественных переменных.
          Несущественные переменные удаляются следующим образом:
          Сначала строится таблица значений функции f(x1, …, xn). Затем перебираются пары строк аргументов, на которых значения функции f(x1, …, xn) совпадают, и отмечается i-й элемент строк вида
             
          Если, в результате, все элементы некоторого столбца j окажутся отмеченными, то xi будет несущественной переменной.

      Пример
             f(x1, x2, x3) = x1 + x3 + x1x2 + x1x2 2 mod 2. Здесь x mod 2 обозначает остаток от деления x на 2. Составим таблицу значений:

x1 x2 x3 f
1 0 0 0 0
2 0 0 1 1
3 0 1 0 0
4 0 1 1 1
5 1 0 0 1
6 1 0 1 0
7 1 1 0 1
8 1 1 1 0
          Строку 1 сравниваем со строками, в которых f = 0. Отмечаем элементы 2-го столбца строк 1 и 3. То же самое проделываем с остальными строками. Отмечаем элементы 2-го столбца строк 2 и 4, 5 и 7, 6 и 8. Поскольку все элементы столбца 2 отмечены, то x2 – несущественная переменная. Вычеркивая второй столбец, получаем таблицу значений некоторой функции g(x, x3), равной f(x1, x2, x3):
x1 x2 g
0 0 0
0 1 1
1 0 1
1 1 0
          Функция g(x1, x3) фиктивных переменных не имеет. В общем случае некоторые строки таблицы значений могут отличаться лишь одним элементом, а функция может не иметь фиктивных переменных. Например, функция f(x1, x2) = x1x2 имеет таблицу:
x1 x2 f
0 0 0
0 1 0
1 0 0
1 1 1

и не имеет фиктивных элементов.


Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности


3. Специальные булевы функции

          Рассмотрим следующие специальные булевы функции, на основе которых могут быть построены другие:
             0, 1 – константы, могут рассматриваться как булевы функции от любого числа переменных n і 0;
             x1 – тождественная функция (или проекция x(x, ..., xn) = x1);
             Шx1 = 1 - x1 – отрицание, обозначается также ;
             x1 & x2 = x1x2 – конъюнкция;
             x1 Ъ x2 = x1 + x2 - x1x2 – дизъюнкция;
             x1 Е x2 = x1 + x2 mod 2 – сложение по модулю 2;
             x1 Ї x2 = (1 - x1)(1 - x2) – стрелка Пирса;
             x1 ~ x2 = (1 - x1)(1 - x2) + x1x2 – эквивалентность;
             x1 ® x2 = 1 - x1 + x1x2 – импликация;
             x1 | x2 = 1 - x1x2 – штрих Шеффера.
          Эти функции можно определить с помощью таблиц истинности:

x1 x2 & Ъ Е Ї ~ ® | Ш 0 1
0 0 0 0 0 1 1 1 1 1 0 1
0 1 0 1 1 0 0 1 1 1 0 1
1 0 0 1 1 0 0 0 1 0 0 1
1 1 1 1 0 0 1 1 0 0 0 1


Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

4. Реализация функций формулами

          Пусть F = {f1, …, fm} – множество булевых функций. Понятие формулы над F определяется индуктивно:

  1. Каждая переменная xi и каждая булева функция из F являются формулами над F.
  2. Если t1, t2, …, tn – формулы над F, то для каждой функции f(x1, …, xn) из F выражение вида f(t1, t2, …, tn) являются формулой над F.

          Каждой формуле над F соответствует булева функция, которая называется интерпретацией этой формулы. Интерпретацию, как и формулу, можно определить индуктивно:

  1. Интерпретация формулы xi сопоставляет элементу (a1, …, an) О I n элемент ai О I.
  2. Интерпретация формулы f(t1, …, tn) принимает значения f(t1(a1, …, ak), …, tn(a1, …, ak)), где функции ti дополняются, в случае необходимости, фиктивными переменными.

      Пример
          Пусть F = {f1(x1, x2) = x1 + x2 - x1x2, f2(x1, x2) = x1x2, f3(x1) = 1 - x1}. Тогда g1(x1, x2, x3) = x1 + x3 - x1x3, g2(x1, x2) = 1 - x1x2, g3(x1) = 1 - x12 и g4(x1, x2) = 1 - x1 – формулы над F, ибо
             
          Подставляя x1, x2, x3 О I в формулы, получим значения интерпретаций этих формул.
          Если интерпретацией формулы g является булева функция f, то формула g называется реализацией функции f. Две формулы называются равносильными, если их интерпретации равны.
          Например, формулы x1 ® (x2 ® x1) и 1, над F = {x1 ® x2, 1}, равносильны, ибо функция g(x1, x2) = (x1 ® (x2 ® x1)) принимает значения 1, для всех x1, x2 О I.
          Множество классов равносильных формул составляют булеву алгебру относительно операций:

&, Ъ, Ш,

которая называется алгеброй Линденбаума – Тарского.
          В следующем разделе будет доказано, что все булевы функции реализуемы формулами над F = {&, Ъ, Ш}, поэтому классы равных булевых функций можно рассматривать как элементы этой булевой алгебры.

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

 

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

      Теорема. Каждая булева функция f : I n ® I реализуема с помощью формулы над .
          Доказательство. Функция 0 реализуема с помощью формулы: . В общем случае имеет место равенство: , где x1обозначает x, а . Здесь обозначает логическую сумму всех значений функции y : I n ® I. Это приводит к равенству, доказывающему теорему: .
          Правая часть этого равенства называется совершенной дизъюнктивной нормальной формой (СДНФ).

      Пример 1
          Найдем СДНФ для функции x1 Ї x2. С этой целью составим таблицу истинности:

x1 x2 x1 Ї x2
0 0 1
0 1 0
1 0 0
1 1 0
          Поскольку лишь на элементе (0, 0) О I 2 значение функции x1 Ї x2 равно 1, то .
          Конъюнктивная нормальная форма определяется как конъюнкция формул вида: . В силу равенств получаем соотношение:
             .
          Это представление функции f называется ее совершенной конъюнктивной нормальной формой (СКНФ).

      Пример 2
          Найдем СКНФ функции . Составим таблицу истинности:
x1 x2 x1 ® x2
0 0 1
0 1 1
1 0 0
1 1 1
         

Так как f(a1, a2) = 0 лишь в случае a1 = 1 и a2 = 0, то СКНФ будет равна: . Заметим, что СКНФ формулы x1 ® x2 будет равна: . Система булевых функций F называется полной, если каждая булева функция реализуема с помощью формулы над F. Поскольку , то имеет место следствие.
          Следствие. Системы функций {Ъ, Ш}, {&, Ш}, {®, Ш} являются полными.

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

6. Минимизация методом карт Карно

          Карты Карно – это графическое изображение таблиц истинности.
          Пусть задана функция f(x1, …, xn). Подмножество элементов (a1, …, an) О I n, в которых f(a1, …, an) = 1, называется носителем функции f и обозначается через supp(f). Конечные пересечения подмножеств вида: I p ґ {ai} ґ I n-p-1 называются кубиками. Кубики будут равны: , для некоторых (s0, s1, sm) и (b1, …, bm) О I n, таких, что s0 + s1 + ... + sm + m = n. Если кубики являются максимальными, содержащимися в носителе, и попарно не пересекаются, то формула
             
будет давать разложение в дизъюнктивную нормальную форму, минимальное по количеству слагаемых. Карты Карно позволяют “увидеть” эти кубики. Для функций двух, трех и четырех переменных они имеют следующие структуры:

x2 0 1
x1

0

f(0,0) f(0,1)

1

f(1,0) f(1,1)
f(1,1,1)
x2 x 00 01 11 10
x1

0

f(0,0,0) f(0,0,1) f(0,1,1) f(0,1,0)

1

f(1,0,0) f(1,0,1) f(1,1,0)
х3 х4 00 01 11 10
х1 х2

00

f(0,0,0,0) f(0,0,0,1) f(0,0,1,1) f(0,0,1,0)

01

f(0,1,0,0) f(0,1,0,1) f(0,1,1,1) f(0,1,1,0)

11

f(1,1,0,0) f(1,1,0,1) f(1,1,1,1) f(1,1,1,0)

10

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

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

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности


      Пример
          Для булевой функции:
             
найти дизъюнктивную нормальную форму с наименьшим числом логических слагаемых.
          Решение. Составим карту Карно:

х3 х4 00 01 11 10
х1 х2

00

1 0 0 1

01

0 0 1 0

11

0 0 1 0

10

1 0 0 1
         

Получаем 2 кубика: {0000, 0010, 1000, 1010} и {0111, 1111}. Внутри первого кубика не изменяются переменные х2 и х4, и равны 0. Значит, первое слагаемое равно: . Внутри второго кубика не изменяются х2 = 1, х3 = 1 и х4 = 1, откуда второе слагаемое равно: х2х3х4. Следовательно, искомая дизъюнктивная нормальная форма равна:

Теги: Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности

up

Комментарии для "Булевы функции. минимизация булевой функции, конъюнкция, таблица истинности,дизъюнкция"


Пользователь: snicky
Сообщений: 1
Статус: Незримый
Зарегистрирован:
22 ноября 2008, 19:03
Был:22 ноября 2008, 19:17
snicky
smsup
Дата: 22 ноября 2008, 19:09 Сообщение № 1
а можно код програмы написать?