Дизъюнктивная нормальная форма ВИННИКОВ В. Э. МАОУ СШ «КОМПЛЕКС «ПОКРОВСКИЙ»

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



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

Для определения истинности или ложности сложного логического выражения используют таблицы истинности. Количество строк напрямую зависит от количества.
Логические законы и правила преобразования логических выражений.
ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ 33. Упрощённо можно представить работу компьютера как некоторого устройства, производящего обработку двоичных сигналов, соответствующих.
Алгебра логики. Логика Логика – это наука о формах и законах человеческой мысли, о законах доказательных рассуждений, изучающая методы доказательств и.
Презентация Сырцовой С.В.. ВСПОМНИМ ПРОШЛЫЙ УРОК Как выглядит таблица истинности для операции ЭКВИВАЛЕНТНОСТИ? С помощью какой связки слов составляется.
Логические функции (логические операции, логические союзы) Инверсия (логическое отрицание) НЕ ( A ) Дизъюнкция (логическое сложение) ИЛИ ( А ; В ) Конъюнкция.
логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда.
Логика – это наука о формах и законах человеческой мысли, о законах доказательных рассуждений, изучающая методы доказательств и опровержений, т. е. методы.
Основы алгебры логики. Лекция 2. Алгоритм построения таблицы истинности 1. Подсчитать количество переменных n в логическом выражении; 2. Определить число.
ГБПОУ «МСС УОР 2» Москомспорта Преподаватель информатики Володина М.В г.
Сложные высказывания можно записывать в виде формул. Для этого простые логические высказывания нужно обозначить как логические переменные буквами и связать.
Основы логики Основы логики Автор: Соколов Кирилл Дата: г. Учитель: Ковалева Ю.В.
1. Подсчитать количество переменных в логическом выражении. 2. Определить число строк в таблице m = 2 n 3. Подсчитать количество логических операций в.
Построение таблиц истинности логических выражений.
Основные понятия алгебры логики. Логические операции. Урок 1: Урок 1:
Логические операции и таблицы истинности Учитель информатики Поборцева Елена Валентиновна.
Элементы математической логики. Высказывание Объект изучения – высказывание. Высказывание – предложение (сообщение) об объективно существующей действительности,
Законы логики. Ответьте на вопросы: Как выглядит таблица истинности для операции ЭКВИВАЛЕНТНОСТИ? С помощью какой связки слов составляется высказывание.
Алгебра логики.. Логика Логика – это наука о формах и способах мышления. Основные формы мышления – понятие, высказывание, умозаключение.
Транксрипт:

Дизъюнктивная нормальная форма ВИННИКОВ В. Э. МАОУ СШ «КОМПЛЕКС «ПОКРОВСКИЙ»

Допустим у нас есть некоторая логическая функция F(x, y, z), которая задана своей таблицей истинности логических переменных. То есть она напрямую зависит от их значений, но формула неизвестна XYZF

Попробуем её выразить формульно, на базе каких-либо логических операций XYZF На самом деле достаточно всего одной операции для формирования любой логической функции. Мы с вами будем пользоваться классическим набором: И, ИЛИ, НЕ Этого достаточно, чтобы любую логическую функцию выписать как логическое выражение.

Итак... Рассмотрим следующие логические выражения XYZFX*Y*Z Очевидно, x*y*z истинна, только в последней строке, во всех остальных случаях она ложна. То есть, казалось бы все эти выражения не похожи, но не совсем так, они похожи именно в последней строке. Более того у нас появился алгоритм, как вставить 1 в нужную строчку.

XYZFX*Y*Zне X*неY*нет Давайте теперь добавим выражение, чтобы было соответствие первой строке, истина, там получается умножение с отрицанием каждого элемента. НеX *неY* нет. В остальных строчках она ложна.

XYZFX*Y*ZнеX*неY*нетнеX*Y*нет Теперь нам нужно придумать такую функцию для третьей строки: получается нам подходит: неX*Y* нет

XYZFX*Y*ZнеX*неY*нетнеX*Y*нетX*неY*Z Наконец, для последней 1 подходит выражение X*неY*Z

Для удобства обозначим все умножения буквами A, B, C, D. Очевидно, что если мы сложим их, то получим значение, соответствующие столбцу F. То есть F =X*Y*Z+неX*неY*нет+неX*Y*нет+X*неY*Z XYZFABCDA+B+C+D

Выразить одну и туже функцию существует большое множество возможностей, например, если к получившейся у нас функции прибавить X*не X, то функция останется неизменной.

Попробуем упростить полученную функцию. F =X*Y*Z+неX*неY*нет+неX*Y*нет+X*неY*Z= X*Z*(Y+неY)+неX*нет*(Y+неY)= X * Z + неX* нет = X=Z 1.Посмотрим, что можно вынести за скобки. X*Y*Z и X*неY*Z. 2. Второе пока остаётся на месте 3.Y+неY сокращается по закону исключённого третьего. 4. У нас получилась функция, которая не зависит от Y. 5. По эквивалентности получилось X = Z, то есть F(x,y,z)=(x=z)

Задание: Построить конъюнктивную нормальную форму, работая со строками с «0».