Истинностное значение формулы

Пример

Имеем формулы

1)

2)

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

Интерпретация = модель + значение свободной переменной, а модель = объектное множество + значение предикатного символа.

Для формулы 1)зададим следующую интерпретацию:

(I): А: 5>3

B: 3>0

C: 4<3

По соглашению о скобках имеем

Следовательно ()^(I)=Л

Чтобы задать интерпретацию (I) Для формулы 2) необходимо:

а) Задать значение предикатного символа

, R

б) Задать объектное множество

x,y

в) Задать свободную переменную

y=2

Ф(2)^(I)=И Ф(10)^(I)=Л

– модель, на которую интерпретируются формулы , т.е. в нашем случае

– истинное значение

– ложное значение

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

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

A	B	C
И	И	И	И
Л	Л
Л	И	И
Л	Л
Л	И	И	И
Л	Л
Л	И	Л
Л	Л

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

Для формулы алгебры предикатов этого сделать нельзя, т.к.:

1) Не все множества конечны

2) Нас интересуют все возможные множества

Однако мы можем построить ограниченную таблицу истинности для частного случая, когда носителем алгебры предикатов является конечное множество:

Пример

Имеем одноместный предикат Ф(у) и объектное множество A={0,1}

Y	L1	L2	L3	L4
	Л	И	Л	И
	Л	Л	И	И

В этом случае имеем 4 варианта формул определения одноместного предиката.

Множество упорядоченных пар отображается на булево множество И, Л

{<00>, <01>, <10>, <11>} {И, Л}

В случае объектного множества A={0,1, 2} имеем 8 вариантов определения одноместного предиката.

Y	L1	L2	L3	L4	L5	L6	L7	L8
	Л	И	Л	И	Л	И	Л	И
	Л	Л	И	И	Л	Л	И	И
	Л	Л	Л	Л	И	И	И	И

 

Выполнимость формул

В алгебре высказываний формула называется выполнимой, если имеется набор истинности значений атомов, при которых значение формулы истинно.

В алгебре предикатов формула выполнима, если существует интерпретация формулы, при которой она истинна.

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

F = (A,B,C)

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

Если ни в одной из интерпретаций формула не принимает истинного значения, то она является невыполнимой. Такая формула называется противоречие.

Пример

Ни при каком значении атома А формула не принимает истинного значения

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

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

Примеры

Логические законы

1) – закон отрицания отрицания

2) – закон отрицания противоречия

3) – закон исключенного третьего

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

1)

Доказательство:

а) для , т.е.

также истинно, т.к. истинно при любых значениях объектных переменных

имеем импликацию вида И И=И

Если предикат является истинным для всех значений индивидной переменной, то формула истинна.

Б) Существуют значения индивидных переменных, при которых P(x) будет ложным

т.к. ложная посылка импликацию дает истину.

2)

Доказательство

а) Существуют значения индивидных переменных, для которых предикат P(y) истинен, тогда

, т.к. заключение истинно

б) , для

Тогда

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

Нахождение всех общезначимых формул – основная задача алгебры логики.

 

Отношение следования

Следование формулы В из формулы А будем обозначать:

1) Формула В следует из формулы А если в любой интерпретации, в которой формула А истинна, формула В также истинна.

Пример

Чтобы в этом убедиться, необходимо построить таблицу истинности.

2) Формула А следует из множества формул Г= если во всех интерпретациях, в которых формулы истинны, формула А также истинна.

, … И

(Здесь и далее символ будет соответствовать словесной формулировке «если…, то…»)

Пример

Убедиться можно аналогично, построив таблицу истинности.