У нас есть два значения: T и F.
Мы можем объединить эти значения тремя способами: NOT, AND и OR.
NOT является самым простым:
Мы можем записать это как таблицу истинности :
when given.. | results in...
============================
T | F
F | T
Для краткости
x | NOT x
=========
T | F
F | T
Думайте о NOT как о дополнении , то есть оно превращает одно значение в другое.
AND работает с двумя значениями:
x y | x AND y
=============
T T | T
T F | F
F T | F
F F | F
AND равен T только в том случае, если оба его аргумента (значения x и y в таблице истинности) равны T - и F в противном случае.
OR равно T, если хотя бы один из его аргументов равен T:
x y | x OR y
=============
T T | T
T F | T
F T | T
F F | F
Мы можем определить более сложные комбинации. Например, мы можем написать таблицу истинности для x AND (y OR z), и первая строка будет ниже.
x y z | x AND (y OR z)
======================
T T T | ?
Как только мы знаем, как оценивать x AND (y OR z), мы можем заполнить оставшуюся таблицу.
К оцените комбинацию, оцените фигуры и отработайте оттуда. Скобки показывают, какие части нужно оценить в первую очередь. То, что вы знаете из обычной арифметики, поможет вам разобраться. Скажем, у вас есть 10 - (3 + 5). Сначала вы оцениваете часть в скобках, чтобы получить
10 - 8
и оцените это как обычно, чтобы получить ответ, 2.
Оценка этих выражений работает аналогично. Мы знаем, как OR работает сверху, поэтому мы можем немного расширить наш стол:
x y z | y OR z | x AND (y OR z)
===============================
T T T | T | ?
Теперь мы почти вернулись к столу x AND y. Мы просто подставляем значение y OR z и оцениваем. В первом ряду у нас есть
T AND (T OR T)
, что совпадает с
T AND T
что просто T.
Мы повторяем один и тот же процесс для всех 8 возможных значений x, y и z (2 возможных значения x умножить на 2 возможных значения y умножить на 2 возможных значения z ) чтобы получить
x y z | y OR z | x AND (y OR z)
===============================
T T T | T | T
T T F | T | T
T F T | T | T
T F F | F | F
F T T | T | F
F T F | T | F
F F T | T | F
F F F | F | F
Некоторые выражения могут быть более сложными, чем они должны быть. Например,
x | NOT (NOT x)
===============
T | T
F | F
Другими словами, NOT (NOT x) это эквивалент просто x.
Правила Деморгана - это удобные приемы, которые позволяют нам преобразовывать эквивалентные выражения, соответствующие определенным шаблонам:
NOT (x AND y) = (NOT x) OR (NOT y)NOT (x OR y) = (NOT x) AND (NOT y)
(Вы можете думать об этом как о том, как NOT распределяется через простые выражения AND и OR.)
Ваш здравый смысл, вероятно, уже понимает эти правила! Например, подумайте о том, что «народ не может быть в двух местах одновременно». Мы могли бы сделать его подходящим для первой части первого правила:
NOT (here AND there)
Применяя правило, это еще один способ сказать: «тебя здесь нет или тебя нет».
Упражнение: Как вы можете выразить второе правило простым английским языком?
Для первого правила давайте посмотрим на таблицу истинности для выражения в левой части знака равенства.
x y | x AND y | NOT (x AND y)
=============================
T T | T | F
T F | F | T
F T | F | T
F F | F | T
Теперь правая сторона:
x y | NOT X | NOT Y | (NOT x) or (NOT y)
========================================
T T | F | F | F
T F | F | T | T
F T | T | F | T
F F | T | T | T
Окончательные значения одинаковы в обеих таблицах. Это доказывает, что выражения эквивалентны.
Упражнение: Докажите, что выражения NOT (x OR y) и (NOT x) AND (NOT y) эквивалентны.