6) Построение одноразрядного двоичного сумматора.

p = f(x, y) = x&y

__ __

z = f(x, y) = x&y Ú x&y

Минимизировать z не представляется возможным, для представления z используют совершенную конъюнктивную нормальную форму (СКНФ).

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

__ __

z = f(x,y) = (x Ú y)&(x Ú y)

Для дальнейшего упрощения воспользуемся законом де Моргана:

Решение логических (содержательных) задач

Одним из разделов логики является алгебра высказываний.

Высказывание – это предложение, о котором однозначно можно сказать истинно оно или ложно. Бывают простые и сложные (составные).

Основная задача – на основании истинности или ложности простых высказываний определить истинность и ложность составных высказываний.

Составление высказываний

Пример 1: Я поеду в Москву и если встречу там друзей, то интересно проведем время.

Решение: М – я поеду в Москву

В – я встречу там друзей М×( В ® И )

И – мы интересно проведем там время

Пример2: Если я поеду в Москву и встречу там друзей, то интересно проведем время.

Решение: М×В ® И

Пример 3: Не верно, что если дует ветер, то солнце светит только тогда, когда нет дождя.

Решение: В – дует ветер

Д – идет дождь

С – светит солнце

Пример 4: Если будет солнечная погода, то ребята пойдут в лес, а (и ) если пасмурная , то - в кино.

Решение: Л – лес

П – солнечная погода

К – кино

Пример 5: Не верно, что если погода пасмурная, то дождь идет тогда и только тогда, когда нет ветра.

Решение: Д – идет дождь

П – пасмурная погода

В – дует ветер

Решение логических задач

I способ – с помощью таблиц истинности

Пример 6: Компьютер вышел из строя (нет изображения на экране монитора), однако неизвестно какое устройство не работает (монитор, видеокарта или оперативная память). Можно предположить следующее:

1) если монитор исправен или видео карта несправна, то оперативная память неисправна;

2) если монитор исправен, то оперативная память исправна.

Исправен ли монитор?

Решение:

1. рассмотрим простые высказывания:

М = Монитор неисправен

В = Видеокарта неисправна

О = Оперативная память неисправна

2. Запишем на языке алгебры логики наши предположения:

3. Пусть F(М,В,О) =

4. Решить данную задачу – значит :

- составить таблицу истинности

- указать, при каких значениях М полученное сложное высказывание истинно.

Необходимо проанализировать все строки таблицы истинности, где F=1.

5. Составим для данного высказывания таблицу истинности: (самостоятельно)

Анализ таблицы показывает, что сложное высказывание истинно во всех случаях, когда М – истинно, т.е. вероятнее всего неисправен именно монитор.

II способ – с помощью преобразования логических выражений

Пример 7: Виктор, Роман, Леонид и Сергей заняли на математической олимпиаде четыре первых места. Когда их спросили о распределении мест, они дали три таких ответа:

1) Сергей – первый или Роман – второй

2) Сергей – второй или Виктор – третий

3) Леонид – второй или Виктор – четвертый.

Известно, что в каждом ответе только одно утверждение истинно.

Как распределились места?

Решение:

Рассмотрим простые высказывания

S1 = Сергей занял первое место

R2 = Роман занял второе место

S2 = Сергей занял второе место

V3 = Виктор занял третье место

L2 = Леонид занял второе место

V4 = Виктор занял четвертое место

На языке алгебры логики ответы ребят можно записать следующим образом:

Конъюнкция истинных высказываний истинна. Следовательно, имеет место равенство:

Раскрыв скобки и упростив это равенство (выполнить самостоятельно), получим:

Другими словами, места на олимпиаде распределились так:

Сергей - 1 место; Леонид – 2 место; Виктор – 3 место; Роман – 4 место.