Презентация Булевы функции и алгебра логики. Двойственность булевых функций онлайн

Содержание слайда: Булевы функции и алгебра логики. Двойственность булевых функций

Содержание слайда: Тема 1 Булевы функции и алгебра логики

Содержание слайда: Булевы переменные и функции Переменные, которые могут принимать значения только из множества B={0,1}, называются логическими или булевыми переменными. Сами значения 0 и 1 булевых переменных называются булевыми константами.

Содержание слайда: Булевы переменные и функции Функция вида y=f(x1,x2,...,xn), аргументы и значения которой заданы на множестве B, называется n-местной булевой функцией. Такие функции также называют логическими или переключательными функциями.

Содержание слайда: Основные определения Кортеж (x1,x2,…,xn) конкретных значений булевых переменных называется двоичным словом (n-словом) или булевым набором длины n. Для булевой функции y=f(x1,x2,…,xn) конкретное (индивидуальное) значение булевого набора (x1,x2,…,xn) называется также интерпретацией булевой функции f. Множество всех двоичных слов, обозначаемое через Bn, образует область определения булевой функций и называется n-мерным булевым кубом и содержит 2n элементов-слов: |Bn|=2n. Каждому двоичному слову соответствует одно из двух возможных значений (0 или 1), таким образом, область значений представляет собой кортеж длиной 2n, состоящий из 1 и 0.

Содержание слайда: Способы задания булевых функций I. Таблицы истинности Таблицы, в которых каждой интерпретации функции поставлено в соответствие ее значение, называются таблицами истинности булевой функции. В таблице истинности каждой переменной и значению самой функции соответствует по одному столбцу, а каждой интерпретации — по одной строке. Количество строк в таблице соответствует количеству различных интерпретаций функции.

Содержание слайда: Булевы функции одной переменной 0 0 — функция константа 0, 1 = x — функция повторения аргумента, 2 =   — функция инверсии или отрицания аргумента, 3  1 — функция константа 1.

Содержание слайда: Булевы функции двух переменных

Содержание слайда: Булевы функции двух переменных

Содержание слайда: Булевы функции двух переменных

Содержание слайда: Способы задания булевых функций II. Номера булевых функций и интерпретаций Каждой функции присваивается порядковый номер в виде натурального числа, двоичный код которого представляет собой столбец значений функции в таблице истинности. Младшим разрядом считается самая нижняя строка (значение функции на интерпретации (1,1,…,1)), а старшим — самая верхняя (значение функции на интерпретации (0,0,…,0)).

Содержание слайда: Способы задания булевых функций Каждой интерпретации булевой функции присваивается свой номер – значение двоичного кода, который представляет собой интерпретация. Интерпретации, записанной в верхней строке таблицы истинности, присваивается номер 0, затем следует интерпретация номер 1 и т.д. В самой нижней строке расположена интерпретация с номером 2n–1, где n — количество переменных, от которых зависит булева функция.

Содержание слайда: Пример Найти порядковый номер функции f(x,y), принимающей следующие значения: f(0,0)=1, f(0,1)=1, f(1,0)=0, f(1,1)=1.

Содержание слайда: Пример Построить таблицу истинности для функции f198

Содержание слайда: Способы задания булевых функций III. Задание булевых функций с помощью формул Формула – это выражение, задающее некоторую функцию в виде суперпозиции других функций. Суперпозицией называется прием получения новых функций путем подстановки значений одних функций вместо значений аргументов других функций.

Содержание слайда: Пример Рассмотрим формулу булевой алгебры, задающую некоторую функцию f(x,y,z) Эта формула содержит функции: g(x1) – отрицание, s(x1,x2) – конъюнкция, l(x1,x2) – дизъюнкция. Представим данную формулу в виде суперпозиции указанных функций следующим образом: f (x,y,z) = l(s(x,g(y)),z)

Содержание слайда: Приоритет выполнения операций Если в формуле отсутствуют скобки, то операции выполняются в следующей последовательности: Отрицание. Конъюнкция. Дизъюнкция. Импликация. Эквивалентность

Содержание слайда: Эквивалентные формулы Формулы, представляющие одну и ту же функцию, называются эквивалентными или равносильными.

Содержание слайда: Законы и тождества алгебры логики 1) Коммутативность конъюнкции и дизъюнкции xy = yx Доказательство xy = yx Доказательство 2) Ассоциативность конъюнкции и дизъюнкции x(yz)= (xy)z Доказательство x(yz)=(xy)z Доказательство 3) Дистрибутивность конъюнкции и дизъюнкции относительно друг друга x(yz) = (xy)(xz) Доказательство x(yz) = (xy)(xz) Доказательство

Содержание слайда: Законы и тождества алгебры логики 4) Идемпотентность конъюнкции и дизъюнкции xx = xx = 5) Закон исключенного третьего Доказательство 6) Закон противоречия Доказательство 8) Закон элиминации x(xy) = Доказательство x(xy) = Доказательство

Содержание слайда: Законы и тождества алгебры логики 7) Тождества с константами. x0 = x1 = x1 = x0 = 9) Закон двойного отрицания. 10) Законы де Моргана. Доказательство Доказательство

Содержание слайда: Тема 2 Двойственность булевых функций

Содержание слайда: Двойственные булевы функции Функция f*(x1,…,xn) называется двойственной к функции f(x1,…,xn), если Пример построения двойственной функции

Содержание слайда: Самодвойственные булевы функции Функция, равная своей двойственной, называется самодвойственной. f = f*

Содержание слайда: Является ли функция f(x,y,z) самодвойственной? Является ли функция f(x,y,z) самодвойственной?

Содержание слайда: Принцип двойственности Пусть функция F заданна суперпозицией функций f0,…,fn, где nN. Функцию F*, двойственную F, можно получить, заменив в формуле F функции f0,…,fn на двойственные им f0*,…,fn*.

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

Содержание слайда: Пример Пример Найти функцию, двойственную функции Решение

Содержание слайда: Если функции равны, то и двойственные им функции также равны. Если функции равны, то и двойственные им функции также равны. Пусть f1 и f2 – некоторые функции, заданные формулами. Тогда если f1 = f2 , то f1* = f2*