2. Логические функции (Булевы функции) Пример: Устройство для голосования. Комиссия из 3-х человек, (Peeter, Jaan, Mari), голосует по вопросу о принятии.

Презентация:



Advertisements
Похожие презентации
3. Нормальные формы логических функций Нормальной формой логической функции является такая формула, которая считается наиболее наглядной и удобной в использовании,
Advertisements

4. Минимизация логических функций. Карты Карно. Задача минимизации логической функции заключается в том, чтобы найти наиболее компактное её представление.
Булевы функции и алгебра логики. Двойственность булевых функций ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции 4-5 Н.В. Белоус.
Основные понятия алгебры логики Лямин Андрей Владимирович.
Булевы переменные и функции Булевыми переменными называются переменные, принимающие значение 0 или 1. Булевы (или логические) функции оперируют с булевыми.
Таблица истинности. Для каждого логического выражения (логического высказывания) можно построить таблицу истинности, которая определяет его истинность.
1 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Логические основы ЭВМ 10 класс Белоусова Елена Ивановна, учитель.
Булевы переменные и функции Булевыми переменными называются переменные, принимающие значение 0 или 1. Булевы (или логические) функции оперируют с булевыми.
Логические основы вычислительной техники. Таблицы истинности Таблицей истинности называют таблицу значений логической функции для разных сочетаний значений.
Алгебра логики. Логическое умножение, сложение и отрицание. Диденко В.В.
Логические основы компьютеров Логические основы компьютеров Базовые логические элементы Базовые логические элементы.
БАЗОВЫЕ ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ БАЗОВЫЕ ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ ОСНОВНЫЕ ЛОГИЧЕСКИЕ СХЕМЫ Яхина Рита Альфировна преподаватель высшей квалификационной категории.
Алгебра логики. Логика Логика – это наука о формах и законах человеческой мысли, о законах доказательных рассуждений, изучающая методы доказательств и.
Элементы математической логики. Высказывание Объект изучения – высказывание. Высказывание – предложение (сообщение) об объективно существующей действительности,
Основы логики и логические основы компьютера. Формы мышления.
Алгебра логики.. Логика Логика – это наука о формах и способах мышления. Основные формы мышления – понятие, высказывание, умозаключение.
Логика - это наука о формах и способах мышления. Понятие; Понятие; Высказывание; Высказывание; Умозаключение Умозаключение Основные формы мышления:
Основы логики и логические основы компьютера. Формы мышления.
ЛОГИЧЕСКИЕ ФУНКЦИИ И АЛГЕБРА ЛОГИКИ Раздел 10 Электроника Лекция 17 Автор Останин Б.П. Конец слайда Логические функции и алгебра логики. Слайд 1. Всего.
Алгебра высказываний Лекция 2 2. Определение высказывания. Таблица истинности для высказываний Определение 1 Переменная А, принимающая два значения –
Транксрипт:

2. Логические функции (Булевы функции) Пример: Устройство для голосования. Комиссия из 3-х человек, (Peeter, Jaan, Mari), голосует по вопросу о принятии некоторого решения. Решение принимается простым большинством голосов. Высказывание A: Peeter голосует за Высказывание B: Jaan голосует за Высказывание C: Mari голосует за Высказывание D: Решение принято 2.1. Перехед от логики высказываний на язык логических функций Джордж Буль ( ) английский математик и логик

ABCD Таблица истинности (зависимость принятия решения D от значений A, B и C) :

Пусть голосование происходит с помощью дигитального устройства: Peeter нажимает на кнопку устройства (за или против). Кнопка связана с двоичным входом устройства X 1, который принимает соответственно значение "1" или "0". Это отображение высказывания A. Отображениями высказываний B и C являются двоичные переменные X 2 и X 3. Результат (высказывание D) выражается логической функцией f(X 1, X 2, X 3 ). дигитальное устройство Peeter Jaan Mari результат вход выход

X1X1 X2X2 X3X3 f(X 1, X 2, X 3 ) дигитальное устройство X1X1 X2X2 X3X3 f(X 1, X 2, X 3 ) вход выход

В дальнейшем: Вместо высказываний A, B, C,... – используем логические переменные X 1, X 2,..., X n,...,где каждая переменная X i, i = 1, 2,..., n,... X i Вместо формул – логические функции f (X 1, X 2,..., X n ) 0 Определение 2.1 логическая функция n переменных f (X 1, X 2,..., X n ) ставит в соответствие каждому двоичному вектору (или аргумент-вектору) (X 1, X 2,..., X n ) 0,1 n логическое значение 0 или 1: При этом каждую последовательность длины n: (X 1, X 2,..., X n ) называем двоичным вектором.

Частные случаи: n = 2 функция 2-х переменных f (X 1, X 2 ) – это следущее соответствие ( 2 2 = 4) 0 1 множество всех двоичных векторов длины n, ( 2 n ) 0 1

Пример: f (X 1, X 2 ) = (X 2 X 1 ) X 1, X 2 f (X 1, X 2 ) f (X 1, X 2 ) Таблица истинности: диаграмма соответствия

n = 3 функция 3-х переменных f (X 1, X 2, X 3 ) – это следущее соответствие ( 2 3 = 8) 0 1

Пример: f (X 1, X 2, X 3 ) = X 1 &X 2 X 2 & X 3 X 1, X 2, X 3 f (X 1, X 2, X 3 ) Таблица истинности:

f (X1, X2, X3) Диаграмма соответствия:

Число всех различных логических функций f(X 1,X 2,...X n ) : n = 1 K = 4 n = 2 K = 16 n = 3 K = 256 n = 4 K = Если n = 1, то всех различных логических функций K = 4 : X1X1 f1f1 f2f2 f3f3 f4f

Перечислим все 16 различных логических функций 2-х переменных f(X 1, X 2 ): x1x1 x2x2 f0f0 f1f1 f2f2 f3f3 f4f4 f5f5 f6f6 f7f x1x1 x2x2 f8f8 f9f9 f 10 f 11 f 12 f 13 f 14 f

В таблице представлены следущие логические функции: f 0 (X 1, X 2 ) = 0 = X 1 & X 1 & X 2 f 1 (X 1, X 2 ) = X 1 & X 2 f 2 (X 1, X 2 ) = (X 1 X 2 ) f 3 (X 1, X 2 ) = X 1 = X 1 ( X 2 & X 2 ) f 4 (X 1, X 2 ) = (X 2 X 1 ) f 5 (X 1, X 2 ) = X 2 = X 2 ( X 1 & X 1 )......

Логические функции f 1 и f 2 равносильные, если для каждого аргумент-вектора ( X 1, X 2,..., X n ) f 1 (X 1, X 2,..., X n ) = f 2 (X 1, X 2,..., X n ). Области истинности логических функций: Область 1-ниц логической функции V 1 образуют те аргумент- векторы ( X 1, X 2,..., X n ), для которых f(X 1, X 2,..., X n )=1 Область 0-лей логической функции V 0 образуют те аргумент-векторы ( X 1, X 2,..., X n ), для которых f(X 1, X 2,..., X n )=0 Логическая функция тождественно истинная (тавтология), если для каждого аргумент-вектора ( X 1, X 2,..., X n ) f(X 1, X 2,..., X n )=1. Логическая функция тождественно ложная (противоречие), если для каждого аргумент-вектора ( X 1, X 2,..., X n ) f(X 1, X 2,..., X n )=0.

по области 1-ниц: f(X 1, X 2, X 3 ) = (1, 6, 7) 1 – означает, что в 1-ой, 6-ой и 7-ой строках таблицы истинности 1-цы, в остальных строках 0- ли. по области 0-ей: f(X 1, X 2, X 3 ) = (0, 3, 5) 0 – означает, что в 0-ой, 3-ей и 5-ой строках таблицы истинности 0-ли, в остальных строках 1- цы. Cпособы представления логических функций : Таблица истинности Логическое выражение Числовое десятичное представление

Теорема 2.1: каждую логическую функцию можно представить a) дизъюнкцией конъюнкций; b) конъюнкцей дизъюнкциий. Доказательство: a) алгоритм представления дизъюнкцией конъюнкций (4 шага): 1. шаг: по формуле 9.a) заменить все - ции через &-ции, -ции и -ия. 2. шаг: по формуле 8.a) заменить все - ции через -ции и -ния. 3. шаг: если стоит перед скобками, то внести отрицание в скобки по формулам 7.a) или 7.b) (законы дe Moргана): (... &... &...) ( ) (... &... &...) 7.b) 7.a) 4. шаг: если в результате получится конъюнкция дизъюнкциий, то применить дистрибутивность 4.a) и перемножить скобки: ( ) & ( ) &... (... &... &...) (... &... &...)... 4.a)

b) алгоритм представления конъюнкцей дизъюнкциий(4 шага): 1. шаг: по формуле 9.a) заменить все - ции через &-ции, -ции и -ия. 2. шаг: по формуле 8.a) заменить все - ции через -ции и -ния. 3. шаг: если стоит перед скобками, то внести отрицание в скобки по формулам 7.a) или 7.b) (законы дe Moргана): (... &... &...) ( ) (... &... &...) 7.b) 7.a) 4. шаг: если в результате получится дизъюнкция конъюнкциий, то применить дистрибутивность 4.b) и перемножить скобки: ( ) & ( ) &...(... &... &...) (... &... &...)... 4.b) Teoрема доказана.

Примеры: представить логическую функцию a) дизъюнкцией конъюнкций 1) ( (X 1 X 2 ) ( X 1 X 2 ))&X 2 2) ((X 1 X 2 )&( X 2 X 3 )) (X 3 X 1 ) b) конъюнкцей дизъюнкциий 1) X 1 &X 3 X 2 &X 3 X 1 &X 2 &X 3 X 1 & X 3 2) (X 1 X 2 ) ((X 1 & X 2 ) X 3 ) Решение: a) дизъюнкцией конъюнкций 1) ( (X 1 X 2 ) ( X 1 X 2 ))&X 2 = ( ( X 1 X 2 ) ( X 1 X 2 ))&X 2 = =(( X 1 X 2 ) ( X 1 X 2 ))&X 2 = ( X 1 X 2 )&X 2 = X 1 &X 2 X 2 &X 2 = = X 1 &X 2 X 2. 8.a) 5.b)4.a) 5.a)

2) ((X 1 X 2 )&( X 2 X 3 )) (X 3 X 1 ) = = (( X 1 X 2 )&( X 2 X 3 )) ( X 3 X 1 ) = = ( ( X 1 X 2 ) ( X 2 X 3 )) ( X 3 & X 1 ) = = (( X 1 & X 2 ) ( X 2 & X 3 )) (X 3 & X 1 ) = = X 1 & X 2 X 2 & X 3 X 1 & X 3. 8.a) 7.b)7.a) 7.b) b) конъюнкцей дизъюнкциий 1) (X 1 &X 3 X 2 &X 3 ) ( X 1 &X 2 &X 3 X 1 & X 3 ) = = [(X 1 X 2 )&(X 1 X 3 )&(X 3 X 2 )&(X 3 X 3 )] [( X 1 X 1 )& ( X 1 X 3 )&(X 2 X 1 )&(X 2 X 3 )&(X 3 X 1 )& (X 3 X 3 )] = = (X 1 X 2 X 1 X 3 )&(X 1 X 2 X 2 X 1 )&(X 1 X 2 X 2 X 3 )&(X 1 X 2 X 3 X 1 )& & (X 3 X 1 X 3 )&(X 3 X 2 X 1 )&(X 3 X 2 X 3 )&(X 3 X 3 X 1 ) = 4.b) 5.b) b) 11.a) b)

= (X 1 X 2 )&(X 1 X 2 X 3 )&(X 1 X 2 X 3 )&(X 3 X 2 X 1 )&(X 3 X 1 ) = = (X 1 X 2 )&(X 1 X 2 )&(X 3 X 1 ) = 10.b)11.a) 5.a) = (X 1 X 2 )&(X 3 X 1 ). 2) (X 1 X 2 ) ((X 1 & X 2 ) X 3 ) = 8.a) (X 1 X 2 ) ( (X 1 & X 2 ) X 3 ) = = ( X 1 & X 2 ) (( X 1 X 2 ) X 3 ) = 7.a)7.b) ( X 1 & X 2 ) ( X 1 X 2 X 3 ) = 4.b) = ( X 1 X 1 X 2 X 3 ) & (X 2 X 1 X 2 X 3 ) = 5.b) = ( X 1 X 2 X 3 ) & ( X 1 X 2 X 3 ) = 5.a) = X 1 X 2 X 3.