Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

План лекции. Решение задач математической логики

Решение задач математической логики

Лекция №5

1. Упрощение логических функций, заданных
в различной форме

2. Вычисление значения логического выражения
для заданных наборов переменных

3. Построение таблиц истинности булевых
функций

4. Определение тождественности булевых
выражений

 

1. Упрощение логических функций, заданных
в различной форме

Задача 1.

 

Упростить логическую функцию, заданную выражением


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

Речь идет о количестве вхождений каждой переменной. Каждая может входить несколько раз, и чем меньше она входит, тем более оптимальная считается функция по этому критерию.

 

Решение:

Шаг 1.
Первым делом избавимся от инверсии, которая охватывает длинную дизъюнкцию в первой скобке. Для этого используем закон де Моргана:

Инверсия дизъюнкций есть конъюнкция инверсий.

Получаем:

­

Первая скобочка – есть инверсия дизъюнкций, мы приводим ее к конъюнкции инверсий. Таким образом, у нас получается более упрощенное выражение. Но самое главное – избавление от длинной инверсии.

 

 

Шаг 2.
Теперь раскроем скобки, используя дистрибутивный закон:

Дистрибутивность умножения относительно сложения
А & (В ÚС) = (А & В)Ú (А& С)

Получаем:

Шаг 3.
Упростим каждую элементарную конъюнкцию, используя законы:

а) противоречия А& Ā = 0

б) идемпотентности А& А = А

На третьем шаге нужно рассмотреть каждую конъюнкцию и постараться проанализировать, можно ли использовать вышеприведенные законы.

Получаем:

 

Шаг 4.
Наконец, используем законы логического умножения на константу 0:

А & 0 = 0

и логического сложения с константой 0:

А + 0 = A

Получаем:

 

Таким образом,

Ответ:

В итоге видно, что мы существенно упростили формулу.

Задача 2.

Упростить логическую функцию, заданную выражением

Решение:

Шаг 1.
Первым делом избавимся от «длинных» инверсий, используя законы де Моргана

Инверсия дизъюнкций есть конъюнкция инверсий.

Инверсия конъюнкция есть дизъюнкция инверсий.

Получаем:

Красным выделено первое преобразование, зеленым – второе.

Шаг 2.
Теперь используем законы двойного отрицания и ассоциативности (уберем внутренние скобки)

Получаем:

Шаг 3.
Теперь для первой скобки используем закон исключенного Третьего

A + Ā = 1

Дизъюнкция А и не А есть всегда 1. Или событие, или его отрицание должно произойти (или на улице идет дождь, или не идет).

Получаем:

Далее используем законы:

а) с константой «1»: 1 + A = 1

б) ассоциативный (от изменения мест
переменных конъюнкция не меняется)

Ответ:

 

Задача 3.

Упростить логическую функцию F (x, y, z), заданную таблично. Значение функции равно 1 на наборах 000, 001, 010, 011, 111.

x y z F
       
       
       
       
       
       
       
       

 

Решение:

Шаг 1.

Построим СДНФ.

Для этого необходимо единичные наборы преобразовать к набору переменных.

Если значение равно нулю – элемент конъюнкции с инверсией. Если один – без инверсии.

 

Единичные наборы:

000 001 010 011 111

Пишем набор по единичным наборам.

Вместо двоичных значений в таблице мог быть набор в десятичной форме:

0, 1, 2, 3, 7.

 

Теперь Преобразуем СДНФ к более компактному виду.

 

2. Добавим еще одну конъюнкцию, используя закон A+A=A:

 

 

3. Группируем по две конъюнкции и далее используем правило склеивания:

Преобразуем СДНФ к более компактному виду.

<== предыдущая лекция | следующая лекция ==>
Публичную лекцию Ильи Доронченкова | Вычисление значения логического выражения для заданного набора значений переменных
Поделиться с друзьями:


Дата добавления: 2014-01-05; Просмотров: 435; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.