Носырева Л.Л. Дискретная математика. Булевы функции - файл n1.doc

приобрести
Носырева Л.Л. Дискретная математика. Булевы функции
скачать (1254 kb.)
Доступные файлы (1):
n1.doc1254kb.13.09.2012 16:46скачать

n1.doc

  1   2   3
Иркутский государственный технический университет

Факультет Кибернетики

Кафедра Автоматизированных систем


Носырева Л.Л.
ДИСКРЕТНАЯ МАТЕМАТИКА

Конспективный материал к лекциям


(рабочий вариант)
Для специальностей АСУ, МЭИ, ИП, АСОК


Часть 5

Булевы функции


Иркутск 2006

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




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



Функцию f, принимающую одно из двух значений, 0 или 1, от n переменных, каждая из которых принимает одно из двух значений, 0 или 1, будем называть булевой функцией f(x1 ,x2 ,…, xn ) от n переменных.

Иначе говоря, булевой называется функция вида:
f: {0,1}ⁿ? {0,1}.
Множество булевых функций от n переменных будем обозначать .

Любая булева функция может быть задана в виде таблицы истинности. Если значение функции f зависит от n переменных то таблица истинности содержит 2ⁿ строк, соответствующих всем различным комбинациям значений этих переменных.

Рассмотрим, например, устройство, фиксирующее принятие некоторой резолюции комитетом «трех». Каждый член комитета при одобрении резолюции нажимает свою кнопку; если большинство членов согласны, то резолюция принимается, что фиксируется регистрирующим прибором. Устройство реализует функцию f(x1, х2, х3), таблица истинности которой имеет вид табл. 1.
Таблица 1.

x1


х2

х3

f(x1, х2, х3)

x1


х2

х3

f(x1, х2, х3)

0

0

0

0

1

0

0

0

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

0

1

1

1

1

1

1

1


Число булевых функций от n переменных равно числу столбцов, которые можно сопоставить строкам таблиц истинности и равно , т.е. =.

Булевы функции от одной переменной приведены в табл.2.
Таблица 2.

x

f0

f1

f 2

f 3

0

0

0

1

1

1

0

1

0

1

Обозначение

0

х

¬х

1

Название

Конст.0

х

Отрицание х

Конст.1

Построим все булевы функции от двух переменных (табл. 3).
Таблица 3.

Переменные

Булевы функции

x1

x2

f0

f1

f 2

f 3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1



Функция f0(x1, х2) = 0 - константа нуль.

Функция f1(x1, х2) = x1 х2 — конъюнкция,

Функция f2(x1, х2)= - левая коимпликация (читается «не если х1 то х2», префикс ко - от лат. conversus — обратный).

Функция f3(x1, х2) =

Функция f4(x1, х2) = - правая коимпликация.

Функция f5(x1, х2) = .

Функция f6(x1, х2) = - сложение по модулю два или функция неравнозначности, неэквивалентности.

Функция f7(x1, х2) = - дизъюнкция,

Функция f8(x1, х2) = - функция Вебба.

Функция f9(x1, х2) = - функция эквивалент­ности, равнозначности.

Функция f10(x1, х2) = - отрицание.

Функция f11(x1, х2) = - правая импликация (читается «если х2, то x1»).

Функция f12(x1, х2) = - отрицание.

Функция f13(x1, х2) = - левая импликация (читается «если x1 то х2»).

Функция f14(x1, х2) = - функция Шеффера.

Функция f15(x1, х2) = 1 — константа единица.

Условимся называть булевы функции от одной и двух переменных элементарными булевыми функциями.

Булевы функции от одной и двух переменных являются операциями на множестве булевых функций.
  1   2   3


Иркутский государственный технический университет
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации