Математика и информатика (стр. 4 )

Эквиваленция (иногда используется термин «двойная импликация») – бинарная логическая связка по своему применению приближенная к союзам тогда и только тогда, если и только если. Логическая операция эквиваленция записывается так: A « B, X Û Y.

Таблица истинности:

a	b	a↔b
1	1	1
1	0	0
0	1	0
0	0	1

Эквиваленцией (или эквивалентностью) двух высказываний X, Y называется новое высказывание, которое считается истинным, когда оба эти высказывания, либо одновременно истинны, либо одновременно ложны, и ложны во всех остальных случаях. Эквивалентность играет большую роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, т. е. в форме эквивалентности. В этом случае, зная об истинности или ложности одного их двух членов эквивалентности и доказав истинность самой эквивалентности, мы делаем заключение об истинности или ложности второго члена эквивалентности.

Раздел 4. Составление таблиц истинности

Пусть F – некоторая формула логики высказываний. Если каждой переменной, входящей в эту формулу, приписать одно из значений истинности (и либо л), то, пользуясь определениями логических операций, можно найти значение формулы F при данном наборе значений ее переменных.

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

«Дерево перебора значений» и таблица истинности для формулы с двумя переменными:

Подобным образом можно составить таблицу истинности для формулы с тремя и более переменными и убедиться, что для формулы с п переменными таблица будет иметь 2n строк. Количество столбцов в таблице истинности равно сумме числа переменных, входящих в формулу, и количеству логических опе-раций.

Пример 1

Составить таблицу истинности для формулы

(X/\Y) « (Z®X)

Решение.

В этой формуле содержатся три переменные, следовательно, таблица имеет 8 строк всевозможных наборов значений истинности (для упрощения чтения будем использовать 1-истина, 0-ложь).

1.  Переменные, озаглавливающие столбцы, расположим слева направо в алфавитном порядке.

2.  Верхнюю половину первого (крайнего левого) столбца заполним цифрами 1, нижнюю цифрами 0.

3.  Верхнюю четверть второго столбца заполним цифрами 1, следующую за ней цифрами 0, третью четверть цифрами 1 и последнюю цифрами 0.

4.  В третьем столбце цифры 1 и 0 чередуются построчно.

5.  В четвертом столбце заполним значения для Y (отрицание Y).

6.  В пятом столбце заполним значения для X /\ Y (конъюнкция переменных X и отрицания Y).

7.  В шестом столбце заполним значения для Z ® X

(импликация переменных X,Y).

8.  В седьмом столбце заполним значения (X/\Y)« (Z®X) (эквиваленция формул пятого и шестого столбцов).

Таблица истинности для указанной формулы вместе с промежуточными результатами выглядит так:

X	Y	Z	Y	X/\Y	Z®X	(X/\Y)« (Z®X)
1	1	1	0	0	1	0
1	1	0	0	0	1	0
1	0	1	1	1	1	1
1	0	0	1	1	1	1
0	1	1	0	0	0	1
0	1	0	0	0	1	0
0	0	1	1	0	0	1
0	0	0	1	0	1	0

Использование логических функций EXCEL
для составления таблиц истинности

В Excel в категории «логические» имеются функции И (конъюнкция), ИЛИ (дизъюнкция), НЕ (логическое отрицание), а также аргументы ИСТИНА, ЛОЖЬ. Аргументу ИСТИНА соответствует 1, аргументу ЛОЖЬ соответствует 0. Встроенные функции для импликации и эквиваленции отсутствуют, но можно воспользоваться одним из тождеств, которые легко доказываются: X®YºXÚY, X«Yº(XÚY)Ù(YÚX). Есть и другие тождества. Ниже приведен пример таблицы истинности для конъюнкции с использованием функции И. Справа показана замена аргументов на числовые значения, что ускоряет ввод данных.

ЛОЖЬ	ЛОЖЬ	ЛОЖЬ		0	0	ЛОЖЬ
ЛОЖЬ	ИСТИНА	ЛОЖЬ		0	1	ЛОЖЬ
ИСТИНА	ЛОЖЬ	ЛОЖЬ		1	0	ЛОЖЬ
ИСТИНА	ИСТИНА	ИСТИНА		1	1	ИСТИНА

Таблицы с формулами:

=ЛОЖЬ()	=ЛОЖЬ()	=И(A1;B1)		0	0	=И(E1;F1)
=ЛОЖЬ()	=ИСТИНА()	=И(A2;B2)		0	1	=И(E2;F2)
=ИСТИНА()	=ЛОЖЬ()	=И(A3;B3)		1	0	=И(E3;F3)
=ИСТИНА()	=ИСТИНА()	=И(A4;B4)		1	1	=И(E4;F4)

Раздел 5. Формализация высказываний

Как отмечалось выше, вопрос об истинности или ложности составного высказывания должен решаться во всех случаях однозначно. Для формализации высказывания необходимо определить простое оно или составное:

1. Если высказывание простое, то поставить ему соответственно элементарную формулу.

2. Если высказывание составное, то для составления соответствующей формулы нужно:

- выделить все элементарные высказывания и логические связки, образующие данное составное высказывание;

- заменить их соответствующими символами (различные элементарные высказывания обозначаются различными символами);

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

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

Подобным образом формализуются и высказывательные формы.

Пример 2

Запишем следующее высказывание в виде формулы:

«До института можно доехать либо на автобусе, либо на метро».

Решение.

Данное высказывание является составным, так как имеет логические связки ЛИБО. Как уже отмечалось выше, ЛИБО носит исключающий характер (см. примечание). Выделим все элементарные высказывания, входящие в него, и обозначим их:

X – до института можно доехать на автобусе,

Y - до института можно доехать на метро.

Заменим выделенные элементарные высказывания и логические связки соответствующими символами и расставим по смыслу скобки. Получим формулу: (X۸Y)٧(Y۸X).

Пример 3

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

Решение.

Выделим все элементарные высказывания, входящие в него, и обозначим их :

студент сдал необходимые экзамены – X;

студент сдал необходимые зачеты – Y;

студент переводится на следующий курс – Z.

Заменим выделенные элементарные высказывания и логические связки соответствующими символами и расставим по смыслу скобки. Получим формулу (X۸Y)« Z.

Таблица истинности для полученной формулы (см. при-
мер 1) будет следующего вида:

X	Y	Z	X۸Y	X۸Y«Z
1	1	1	1	1
1	1	0	1	0
1	0	1	0	0
1	0	0	0	1
0	1	1	0	0
0	1	0	0	1
0	0	1	0	0
0	0	0	0	1

Раздел 6. Тавтологии

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