uzluga.ru
добавить свой файл



Логической переменной называется переменная, значением которой может быть любое высказывание.

  • Логической переменной называется переменная, значением которой может быть любое высказывание.

  • Пример:

  • x, у, x1, y1, xk, уn



Логической формулой является:

  • Логической формулой является:

  • 1) любая логическая переменная, а также каждая из двух логических констант — 0 (ложь) и 1 (истина);

  • 2) если А и В — формулы, то В и А*В — тоже формулы, где знак «*» означает любую из логических бинарных операций.

  • Пример:

  • (х & у)  z

  • Формуле приписывается одно из двух значений — 0 или 1.



Формулы А и B, зависящие от одного и того же набора переменных x1, х2, х3, … xn, называют равносильными или эквивалентными, если на любом наборе значений переменных x1, х2, х3, … xn они имеют одинаковые значения.

  • Формулы А и B, зависящие от одного и того же набора переменных x1, х2, х3, … xn, называют равносильными или эквивалентными, если на любом наборе значений переменных x1, х2, х3, … xn они имеют одинаковые значения.

  • Пример:

  • А = В



Любую формулу можно преобразовать к равносильной ей, в которой используются только операции &, v и отрицание.

  • Любую формулу можно преобразовать к равносильной ей, в которой используются только операции &, v и отрицание.





x & у = y & x

  • x & у = y & x

  • x v у = y v x



(x & у) & z = x & (у & z)

  • (x & у) & z = x & (у & z)

  • (x v у) v z = x v (у v z)



x v 0 = x

  • x v 0 = x

  • x & 1 = x



x & (у v z) = (x & у) v (x & z)

  • x & (у v z) = (x & у) v (x & z)

  • x v (у & z) = (x v у) & (x v z)



x & x = 0

  • x & x = 0



x v x = 1

  • x v x = 1



x & x = x

  • x & x = x

  • x v x = x



x = x

  • x = x



x & у = x v y

  • x & у = x v y

  • x v у = x & у



x v (x & y) = x

  • x v (x & y) = x

  • x & (x v y) = x



Любой из законов алгебры логики может быть доказан с помощью таблиц истинности.

  • Любой из законов алгебры логики может быть доказан с помощью таблиц истинности.





Законы алгебры логики можно доказать путем логических рассуждений.

  • Законы алгебры логики можно доказать путем логических рассуждений.



Пусть истинна правая часть, т. е. x = 1, тогда в левой части дизъюнкция x v (x & у) истинна по определению дизъюнкции.

  • Пусть истинна правая часть, т. е. x = 1, тогда в левой части дизъюнкция x v (x & у) истинна по определению дизъюнкции.

  • Пусть истинна левая часть. Тогда по определению дизъюнкции истинна или формула x, или формула (x & у), или обе эти формулы одновременно.

  • Если x ложна, тогда (x & у) ложна, следовательно, x может быть только истинной.



Законы алгебры логики можно доказать путем тождественных преобразований.

  • Законы алгебры логики можно доказать путем тождественных преобразований.



x v (x & у ) = (x & 1 ) v (x & у ) = x & (1 v y) = x

  • x v (x & у ) = (x & 1 ) v (x & у ) = x & (1 v y) = x



Формула А называется тавтологией (или тождественно истинной), если она истинна при любых значениях своих переменных.

  • Формула А называется тавтологией (или тождественно истинной), если она истинна при любых значениях своих переменных.

  • Пример:

  • х v х (закон исключенного третьего)



Формула А называется тождественно ложной, если она ложна при любых значениях своих переменных.

  • Формула А называется тождественно ложной, если она ложна при любых значениях своих переменных.

  • Пример:

  • х & х



Отрицание.

  • Отрицание.

  • Конъюнкция.

  • Дизъюнкция (строгая и нестрогая).

  • Импликация и эквивалентность.





F1 = {если одно слагаемое делится на 3 и сумма делится на 3, то и другое слагаемое делится на 3};

  • F1 = {если одно слагаемое делится на 3 и сумма делится на 3, то и другое слагаемое делится на 3};

  • F2 = {если одно слагаемое делится на 3, а другое не делится на 3, то сумма не делится на 3}.

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



x = {одно слагаемое делится на 3};

  • x = {одно слагаемое делится на 3};

  • y = {сумма делится на 3};

  • z = {другое слагаемое делится на 3}.

  • F1 = x & y  z

  • F2 = x & z  y





F1 = {если все стороны четырехугольника равны и один из его углов прямой, то этот четырехугольник является квадратом};



x = {все стороны четырехугольника равны};

  • x = {все стороны четырехугольника равны};

  • y = {один угол четырехугольника прямой};

  • z = {четырехугольник является квадратом}.

  • F1 = x & y  z

  • F2 = x & z  y





a  b = a v b

  • a  b = a v b

  • a ~ b = a & b v a & b

  • a  b = a & b v a & b

  • a  b = b  a

  • a ~ b = (a  b) & (b  a)

  • a  b = a ~ b



























(x v a) v (x v a) = b

  • (x v a) v (x v a) = b



(x v a) v (x v a) =

  • (x v a) v (x v a) =

  • = (x & a) v (x & a) =

  • = (x & a) v (x & a) =

  • = (x & x) v (a & a) =

  • = x & 1 = x

  • x = b

  • x = b



a & a

  • a & a

  • a  (b  a)

  • (a & b)  a









a & (a  b) & (a  b)

  • a & (a  b) & (a  b)