Алгебра логики высказываний Основные понятия

Минимизация булевых функций. Карты Карно Сложность логической функции, как уже было отмечено выше, определяется сложностью ее аналитической записи. Минимальной формой логической функции на некотором множестве фиксированных операций (базисе) можно считать та­кую, которая содержит минимальное число суперпозиций функций базиса, допус­кая и скобки. Однако построить эффективный алгоритм такой минимизации с по­лучением минимальной скобочной формы трудно. Более простой задачей минимизации является нахождение мини­мальная ДНФ функции. Для этой задачи существуют простые эффективные алгоритмы. Один из них основан на применении карт Карно. Карта Карно – это двумерная табличная форма представления булевой функции, позволяющая в наглядной графической форме легко отыскать минимальные ДНФ логических функций. Каждой клетке в таблице сопоставляется дизъюнкт СДНФ ми­нимизируемой функции, причем так, что любым осям симметрии таблицы соот­ветствуют зоны, взаимно инверсные по какой-либо переменной. Такое располо­жение клеток в таблице позволяет легко определить склеивающиеся термы СДНФ (отличающиеся знаком инверсии только одной переменной): они располагаются в таблице симметрично. Например, следующая карта Карно построена для импликации двух переменных х  у. В ячейки карты вписываются значения из таблицы истинности функции, при этом, если перед соответствующей переменной стоит знак отрицания, то в таблице истинности выбирается строка с ложным значением данной переменной, иначе – с истинным значением. Все четыре клетки соответствуют всем воз­можным конъюнкциям СДНФ функции 2 переменных. Единичные значения функ­ции показывают те дизъюнкты, которые присутствуют в СДНФ этой функции. Распо­ложения элементов в картах Карно функции 2 переменных таково, что в один конъюнкт эта переменная входит без отрицания, а в дру­гой – с отрицанием. Алгоритм поиска минимальной ДНФ по карте Карно основан на выявлении на карте минимального количества максимальных квадратов или прямоугольников со сторонами, равными степени двойки, так, чтобы они состояли только из ячеек, содержащих единицы. Для приведенной карты Карно единичные значения покрывают ячейки с координатами  х и у, соответственно искомая минимальная ДНФ будет  х  у. Рассмотрим другую логическую функцию f =  p  q  r  q  (p  r). Знаком  обозначается операция сложения по модулю 2 или «исключающее или» (XOR – eXclusive OR), которая определяется следующим образом: х у х  у 0 0 0 0 1 1 1 0 1 1 1 0 Таблица истинности для данной формулы имеет следующий вид: p q r f 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 Карта Карно для функции трех переменных должна содержать, очевидно, 8 ячеек. Подобную карту можно изобразить следующим образом: Для этой карты Карно единичные значения присутствуют в ячейках с координатами q   r и  q   p, соответственно минимальная ДНФ будет q   r   q   p. В силу симметрии карт Карно при построении прямоугольников возможно объединение ячеек, находящихся в крайних позициях, так как при ином расположении координат строк или столбцов (переменных без отрицания и с отрицанием) крайние ячейки окажутся внутри карты. Следующие две карты Карно эквивалентны (местами поменялись координаты r и  r) и на них указано корректное объединение ячеек в прямоугольные области: Карты Карно также удобны и для минимизации не полностью определенных функций. Например, пусть объявлена функция, у которой не определено часть значений: x y z f 0 0 0 - 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 - 1 1 0 1 1 1 1 - При построении карты Карно для этой функции неопределенные значения можно заменить любыми – 0 или 1. Таким образом, выявляя на карте Карно прямоугольники из единиц, можно использовать ячейки, не содержащие значений. Для данного примера минимальная ДНФ равна y   x.

Похожие:

	1. «Совершенные дизъюнктивные нормальные формы (сднф) и совершенные... Логика – это наука о законах мышления. Это одна из древнейших наук. Основные законы логики были сформулированы еще древнегреческим...		2. Основы логики и логические основы компьютера Основы логики. Основные... Информационные процессы в живой природе, обществе и технике: получение, передача, преобразование, хранение и использование информации....
	«Основные логические элементы» Данный урок является частью темы «Алгебра логики». Необходимость изучения данной темы обусловлена значением переключательных схем...		Рефератов по курсу «Математическая логика и теория алгоритмов» Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
	Программа по дисциплине «прикладные протоколы интернет и www» Глобальные вычислительные сети: os unix – основные понятия, Internet – структура и основные понятия, аппаратное обеспечение, программное...		Урок №47. Формы мышления. Алгебра высказываний. Цели урока Правомерно ли считать, что религия, искусство, наука – духовные истоки философии? Обоснуйте свой ответ
	Конспект урока Тема: Алгебра логики. Решение задач с элементами алгебры логики Планируемый результат: учащиеся решат задачу на движение, используя ос решения текстовой задачи, продемонстрируют уровень усвоения...		Реферат по информатике и икт на тему: «Логика» Что такое алгебра логики стр. 4
	Тема: Основные понятия математической логики Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...		Программа предназначена для преподавателей, ведущих данную дисциплину,... Цель урока: закрепить основные понятия, рассматриваемые в законах механики Ньютона
	«Волшебный компьютер» (35 часов) Свойства информации. Язык представления информации. Кодирование информации. Основные понятия логики. Понятие графов. Устройство персонального...		Урок 1 Тема урока : Логика как наука. Основные понятия математической логики Учебный курс (рабочая программа) «Логика научного исследования» для аспирантов очной и заочной форм обучения специальностей 09. 00....
	Тема : Основные понятия математической логики А представляет собой двоичную запись числа 226, столбец значений аргумента в – числа 154, столбец значений аргумента с – числа 75....		Урок лекция План проведения урока Новое время (индуктивная логика, гипотетико-дедуктивный метод); возникновение математической логики в сер. 19 века. Соотношение традиционной...
	Программа по формированию навыков безопасного поведения на дорогах... Цели Помочь учащимся осознать понятия: грех, гордость, смирение на примере отрывка из Священной истории «Мытарь и Фарисей», высказываний...		Программа по формированию навыков безопасного поведения на дорогах... Мотивы, которые побудили выбрать тему «Алгебра логики и логические элементы персонального компьютера» для создания данного комплекса...