Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Таблицы формул логики высказываний




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

Пусть даны элементарные высказывания Я устал, Я хочу спать и Я могу заниматься, и пусть известно, что первое и третье из них истинны, а второе ложно. Что при этих условиях можно сказать о логическом значении сложного высказывания Если я устал или я хочу спать, то я не могу заниматься?

Поставим элементарным высказываниям в соответствие пропозициональные переменные р, q и r. Высказыванию Я устал или я хочу спать отвечает формула Ú q). Ищем в таблице для дизъюнкции строку, в которой р — истинно, а q — ложно, и находим, что при этих условиях формула Ú q) и соответствующее ей высказывание истинны. Поскольку интересующему нас сложному высказыванию отвечает формула

((p Ú q) ® ~ r),

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

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

Пусть, например,

(((р ® q) Ú r) «((р Ù ~ q) ® ~~ r))

формула и пусть переменные р, q и r принимают соответственно логические значения «ложь», «истина» и «ложь». С помощью таблиц для логических знаков вычисляем последовательно логические значения подформул данной формулы: (p ® q) — «истина», ((p ® q) Ú r) — «истина», ~ q —«ложь», Ú ~ q) — «ложь», ~ r — «истина», ~~ r — «ложь», ((р Ù ~q) ® ~~ ) — «истина», и, наконец, находим, что вся формула имеет логическое значение «истина».

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

 

(((p ® q) Ú r) « ((р Ù ~ q) ® ~ ~ r))
л и и и л и л л л и и л и л

 

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

Составляем список пропозициональных переменных, входящих в данную формулу. Переменные в этом списке должны быть выписаны без повторений. Затем для каждой переменной строим соответствующий ей входной (начальный) столбец таблицы. В каждой строке построенных таким образом входных столбцов выписываем некоторый отличный от остальных набор логических значений для всех пропозициональных переменных. Если n — число входных столбцов, то число строк, содержащих все различные наборы логических значений n переменных, равно 2 n.

Далее, в последовательности, определяемой порядком построения данной формулы из ее подформул, для каждой подформулы, которая отлична от переменной, строим соответствующий ей столбец таблицы. Последний столбец, который называют заключительным (выходным), соответствует данной формуле. Заполнение этих столбцов логическими значениями осуществляется на основе приведенных выше таблиц для логических знаков ~, Ù, Ú, ®, «, ¹.

Построим, например, таблицу для формулы

(p Ù ((q Ú r) ¹ s)).

Так как список пропозициональных переменных этой формулы содержит четыре переменные р, q, r, s, то таблица имеет четыре входных столбца и 16 строк. Остальные три столбца соответствуют всем подформулам данной формулы, отличным от переменных, причем последний является заключительным столбцом. Строки в этих столбцах заполнены на основании таблиц для логических знаков Ú, ¹ и Ù. В результате имеем следующую таблицу.

 

р q r s (q Ú r) ((q Ú r) ¹ s) (p Ù (q Ú r) ¹ s))
и и и и и л л
л и и и и л л
и л и и и л л
л л и и и л л
и и л и и л л
л и л и и л л
и л л и л и и
л л л и л и л
и и и л и и и
л и и л и и л
и л и л и и и
л л и л и и л
и и л л и и и
л и л л и и л
и л л л л л л
л л л л л л л

 

Из таблицы видно, что приведенная формула истинна для четырех наборов логических значений своих переменных и ложна для двенадцати остальных. Она отражает логическую структуру множества конкретных высказываний, в частности, логическую структуру сложного высказывания Он молчит, а Варенька поет ему «Виют витры», или глядит на него задумчиво своими темными глазами, или вдруг зальется: «Ха-ха-ха!». Из шестнадцати возможных (мыслимых) предметных ситуаций, по-разному определяющих логическое значение четырех элементарных высказываний, которые входят в его состав, лишь следующие четыре удовлетворяют условиям, налагаемым на них данным сложным высказыванием: 1) ситуация, при которой он молчит, Варенька смеется, не поет и не глядит задумчиво — этой ситуации отвечает седьмая строка таблицы, в которой р и s — истинны, a q и r — ложны; 2) ситуация, при которой он молчит, Варенька поет, задумчиво глядит и не смеется, — этой ситуации отвечает девятая строка таблицы, в которой р, q и r — истинны, a s — ложно; 3) ситуация, при которой он молчит, Варенька глядит задумчиво, не поет и не смеется, — этой ситуации отвечает одиннадцатая строка таблицы, в которой р и r — истинны, а q и s — ложны; и, наконец, 4) ситуация, при которой он опять-таки молчит, Варенька поет, но не глядит задумчиво и не смеется,— этой ситуации отвечает тринадцатая строка таблицы, в которой р и q — истинны, а r и s — ложны. Данная интерпретация условий истинности сложного высказывания хорошо согласуется с обычным пониманием его смысла.

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

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

Например:

 

(((p Ú q) « ~ q) ® (~ r ® ~ р))
и и и л л и и л и и л и
л и и л л и и л и и и л
и и л и и л и л и и л и
л л л л и л и л и и и л
и и и л л и и и л л л и
л и и л л и и и л и и л
и и л и и л л и л л л и
л л л л и л и и л и и л

 

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

Определение. Таблица формулы А есть таблица с перечнем пропозициональных переменных E1, E2,..., Еn, если: а) переменные выписаны в этом перечне без повторений; б) перечень содержит все пропозициональные переменные, входящие в А, и в нем могут содержаться (не обязательно) пропозициональные переменные, не входящие в А; в) имеется n входных столбцов, по одному для каждой переменной перечня.

Например, для формулы

((р ® r) Ù ~ p)

можно построить следующую таблицу с перечнем пропозициональных переменных р, q, r:

 

р q r ® r) ((р ® r) Ù ~ p)
и и и и л л
л и и л и л
и л и и л л
л л и л и л
и и л л л л
л и л и и и
и л л л л л
л л л и и и

 

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

Легко понять, что таблица формулы с некоторым перечнем переменных содержит (в качестве подтаблиц) таблицы всех своих подформул с тем же перечнем переменных. Так, таблица подформулы


(q Ú r)

формулы

(p Ù ((q Ú r) ¹ s))

образуют 1й, 2й, 3й, 4й и 5й столбцы таблицы на с. 23. Если рассматривать эти пять столбцов в качестве самостоятельной таблицы формулы (q Ú r) с перечнем переменных р, q, r и s, то при желании ее можно минимизировать, вычеркнув столбцы для переменных р и s и устранив образовавшиеся в результате вычеркивания повторяющиеся строки.

 

Упражнения

I. Построить минимальные таблицы истинности для следующих формул:

1) (((~ q ® р) Ú q) «р);

2) (((p Ú q) ¹ r) ® (~q ® r));

3) (r ® ((q Ú s) Ù ~ r)).

II. Построить таблицы истинности с перечнем переменных р, q и r для следующих формул:

1) ((p Ù ~ p) Ú p);

2) (((р Ú q) ® ~р) Ù~ р);

3) ((р «q) ® (q ¹ r)).

III. При каких логических значениях переменных следующие формулы получают значение «ложь»:

1) ((р Ú q) ® ((~ p Ù q) Ú (p Ù ~ q)));

2) (((р Ù ~ q) « ~ r) ¹ ((~ р Ú r) ® q));

3) ((((~р ¹ q) ® ~ r) Ú s) Ù ~ t).

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

следующих формул:

1) (((p Ù q) ® (q Ú r)) Ù (p «~ r));

2) ((((p «r) Ú q) Ù~ p) ® (p Ù~ q));

3) (((р «~ r) ® q) ® ((p «r) Ù ~ r)).






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных