Понедельник, Июль 5th, 2010

МЛОИ

Легко видеть, что эта таблица соответствует определению операции эквиваленции (?), то есть F ?X?Y. Выражая теперь эквиваленцию через конъюнкцию, дизъюнкцию и отрицание, получаем: F??X??Y?X?Y. Техническая реализация схемы дана на рис.13.
Рис.13. Схема, реализующая формулу ?X??Y?X?Y.
Пример 3. Требуется сконструировать систему тайного голосования, в которой используются кнопочные выключатели и лампочка. Голосуют n человек. Лампочка должна загораться, если кнопки нажимают [n/2]+1 человек. (Квадратные скобки обозначают взятие целой части дроби n/2.)
Для простоты возьмем n=3. В таком случае лампочка должна загореться, если кнопки нажмут не менее 2-х человек.
Решение. Пусть X1, X2, X3 — участники голосования, F — лампочка. Если участник голосования c номером i нажимает кнопку, то значением переменной Xi будет И, в противном случае — Л. Если лампочка загорается, то значит значение F равно И, в противном случае- Л.
Построим таблицу истинности искомой схемы:
X1
X2
X3
F
Л
Л
Л
Л
Л
Л
И
Л
Л
И
Л
Л
Л
И
И
И
И
Л
Л
Л
И
Л
И
И
И
И
Л
И
И
И
И
И
Теперь запишем формулу логики высказываний, соответствующую этой таблице истинности.
Прежде заметим, что каждой строке таблицы, в которой F = И, соответствует единственная конъюнкция переменных X1, X2, X3 или их отрицаний, такая, что при соответствующих значениях истинности этих переменных F = И. Так, четвертой строке таблицы соответствует конъюнкция ? X1&X2&X3, которая принимает значение И при X1=Л, X2=И, X3=И, шестой строке — X1&?X2&X3, которая принимает значение И при X1=И, X2=Л, X3=И, и так далее. Такие конъюнкции называют элементарными.
Выпишем все такие конъюнкции для приведенной выше таблицы:
? X1&X2&X3, X1&?X2&X3, X1&X2&? X3, X1&X2&X3.
Очевидно, что искомая формула будет представлять собой дизъюнкцию всех таких конъюнкций:
F = ? X1&X2&X3 ? X1&?X2&X3 ? X1&X2&? X3 ? X1&X2&X3.3)
Выполняя равносильные преобразования этой формулы, получим:
? X1&X2&X3 ? X1&?X2&X3 ? X1&X2&? X3 ? X1&X2&X3 ?
? ?X1&X2&X3?X1&?X2&X3?X1&X2&?X3?X1&X2&X3?X1&X2&X3?X1&X2&X3 ?
?(?X1&X2&X3?X1&X2&X3)?(X1&?X2&X3?X1&X2&X3)?(?X3?X1&X2&X3 X1&X2&X3) ?
? X2&X3&(? X1? X1) ? X1&X3&(? X2? X2) ? X1&X2&(? X3? X3) ?
? X2&X3 ? X1&X3 ? X1&X2 ?
?X1&( X2? X3) ? X2&X3 .
Техническое решение искомой схемы приведено на рис.15. (Контакт X2, который указан дважды на приведенной схеме, обозначает один и тот же контакт. То же самое можно сказать и относительно X3.)

Рис.15. Схема, реализующая формулу X1&( X2? X3) ? X2&X3

Заключение

Таким образом в ходе 4 и 5 лекций были рассмотрены основные понятия логики высказываний: понятие высказывания, истинность и ложность высказываний, простые и составные высказывания. Мы познакомились с основными операциями над высказываниями, со свойствами операций над высказываниями, а также применение логики высказываний к анализу структуры математических доказательств и применение логики высказываний к решению задач анализа и синтеза переключательных (контактных) схем.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Категория: Лекции