Информатика и вычислительная техника
В общем случае операция конъюнкции
В общем случае операция конъюнкции может быть определена для любого числа аргументов: х1 & х2 & ... =
| n |
| & |
| i = 1 |
106
Для дизъюнкции, конъюнкции и отрицания справедливы следующие логические выражения:
В алгебре логики действуют четыре основных закона: переместительный (коммутативный), сочетательный (ассоциативный), распределительный (дистрибутивный) и общей инверсии (правило или формула де Моргана). Приведем соотношения, отражающие эти законы.
1. Переместительный закон:
- - для дизъюнкции х1 ? х2 = x2 ? х1;
- - для конъюнкции х1 & х2 = х2 & х1.
2.. Сочетательный закон:
- - для дизъюнкции (х1 ? x2) ? x3 = х1 ? (x2 ? x3);
- - для конъюнкции (х1 & x2) & x3 = х1 & (x2 & x3).
3, Распределительный закон:
- - для дизъюнкции (x1 ? x2) & x3 = х1 & х3 ? x2 & х3;
- - для конъюнкции (x1 & x2) ? x3 = (х1 ? х3) & (x2 ? х3).
4. Закон общей инверсии (формула де Моргана):
- - для дизъюнкции х1 ? х2 = х1 & х2;
- - для конъюнкции х1 & х2 = х1 ? х2.
Следует отметить, что все приведенные законы, кроме закона общей инверсии и распределительного закона для конъюнкции, полностью аналогичны соответствующим законам для сложения и умножения в обычной алгебре. Такая аналогия отсутствует для формулы де Моргана и для распределительного закона для конъюнкции. Их справедливость можно доказать с помощью таблиц истинности, вычисляя в них значения левой и правой частей доказываемого логического выражения для всех наборов логических переменных.
Докажем, например, справедливость формул де Моргана для дизъюнкции и конъюнкции. С этой целью составим таблицу для четырех наборов переменных x1 и х2, а затем в столбцах этой таблицы вычислим по соответствующим правилам алгебры логики значения левых и правых частей доказываемых формул. Полученные результаты сведем в таблицу.
107
| * | ** | * | ** | ||||||
| x1 | x2 | x1 ? x2 | x1 ? x2 | x1 & x2 | x1 ? x2 | x1 | x2 | x1 & x2 | x1 ? x1 |
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий