Упражнение 5. Найдите главную логическую константу в каждой из следующих формул.

 

Найдите главную логическую константу в каждой из следующих формул.

1. Ú q) Ù r É рÙ r;

2. р ÙØ q É rº рÉ (Ø qÉ r);

3. ((pÉ q) É q) É q;

4. Ø (ØрÚ р ).

 

Построим таблицу истинности для формулы рÚ q ÉØ q. В таблице под главной константой формулы будем писать истинностные значения формулы в целом. В этой формуле главной логической константой является знак импликации. Чтобы установить истинностные значения всей формулы, необходимо установить истинностные значения подформул, составляющих ее, т.е. формул рÚ q и Ø q. Истинностные значения этих формул будем соответственно писать под логическими константами Ú и Ø. В результате получим таблицу истинности:

 

 

p q рÚ q ÉØ q
и и и л л
и л и и и
л и и л л
л л л и и

 

 

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

 

p q рÚ q ÉØ q
и и и л

 

Оказывается, антецедент формулы в целом, являющейся импликацией, имеет значение и, а консеквент — л. В приведенной выше таблице для импликации в этом случае импликация имеет значение л:

 

p q рÚ q ÉØ q
и и и л л

 

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

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

Число строк в таблице истинности определяется по следующей формуле: число строк таблицы = 2n, где п — число различных пропозициональных переменных, входящих в формулу, а число 2 показывает число истинностных значений (и, л).

Учитывая сказанное, построим таблицу истинности для формулы:

É (q É r)) É ((р É q) É É r)).

Формула содержит три различные переменные. Следовательно, число строк в таблице = 2n, 23=8. Разделим число строк пополам и напишем под первой пропозициональной переменной (первой слева) в столбик четыре раза и и четыре раза л:

É (q É r)) É ((р É q) É É r)).

и

и

и

и

л

л

л

л

 

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

É (q É r)) É ((р É q) É É r)).

и и

и ___и_______________________

 

и л

и___ л_______________________

л и

л ___и________________________

л л

л л

 

Разделим, далее, половину каждой половины пополам и под третьей по вхождению слева переменной, отличной от первых двух переменных, напишем и, если эта часть (строка) нечетная при пересчете сверху вниз, или л, если часть (строка) четная:

и

É ( q É r)) É ((р É q) É É r)).

и и __и_____________________

и____и__ л_____________________

и

и л ___и_____________________

и____л__ л_____________________

л и __и_____________________

л____и___л_____________________

л л___и_____________________

л л л

Деление производится до тех пор, пока полученная в результате деления часть не будет состоять из одной строки.

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

É (q É r)) É((р É q) É É r)).

и и___и___и___и___и___и

и___и___л___и___и___и___л

и л___и___и___л___и___и

и___л___л___и___л___и___л

л и___и___л___и___л___и

л___и___л___л___и___л___л

л л___и___л___л___л___и

л л л л л л л

Несложно завершить построение таблицы истинности:

É (q É r)) É ((р É q) É É r)).

и и и и и и__и_и_и_и__и_и_и

и л и__л_л__и__и_и_и_л__и_л_л

и и л и и и__и_л_л_и__и_и_и

и_и__л__и_л__и__и_л_л_и__и_л_л

л и и и и и__л_и_и_и__л_и_и

л и и__л_л__и__л_и_и_и__л_и_л

л и л и и и__л_и_л_и__л_и_и

л и л и л и л и л и л и л

Эта формула имеет значение “истина” при каждом наборе значений входящих в нее переменных.

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

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

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

 








Дата добавления: 2014-12-26; просмотров: 989;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.015 сек.