Тождественно истинная формула это

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

1. Формулы, принимающие значения И при всех наборах входящих в них переменных называются тождественно истинными (ТИФ).

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

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

Предложение «j – тождественно истинная формула» обозначают |‑j.

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

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

1. Во-первых, если число переменных не очень мало, то число наборов, которые нужно подставлять, будет очень велико и применение простого принципа сравнения формул А и В может стать практически невозможным. Уже для 30 переменных потребуется проверить 10 9 наборов (это примерно соответствует 2 30 ). При этом для установления равносильности нужно для каждого набора провести вычисление значений обеих формул, а если эти формулы большой длины, то на это, в свою очередь, понадобится большое число операций.

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

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

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 8955 – | 7623 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

2. 13. Логические формулы и таблицы истинности

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

Тождественно-истинные формулы являются истинными при всех наборах истинностных значений входящих в них переменных (т. е. простых суждений). Любая тождественно-истинная формула представляет собой логический закон.

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

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

Если в результате формализации какого-либо рассуждения получается тождественно-истинная формула, то такое рассуждение является логически верным, или правильным. Причем его правильность будет не случайной, а закономерной, т. к. построение рассуждения в соответствии с тождественно-истинной формулой гарантирует его логическую верность независимо от его содержания, т. е. от того, о чем идет в нем речь. Если же результатом формализации будет тождественно-ложная формула, то рассуждение следует признать логически противоречивым (и, конечно же, неверным, или неправильным). Причем его неправильность будет не случайной, а закономерной, т. к. построение рассуждения в соответствии с тождественно-ложной формулой обусловливает его ошибочность, или логическую неверность независимо от его содержания. Выполнимая или нейтральная формула также свидетельствует о логической неверности того рассуждения, формализацией которого она является. На первый взгляд это может показаться странным, однако дело здесь заключается в том, что рассуждение, построенное в соответствии с выполнимой формулой может приводить как к истинным, так и к ложным выводам в зависимости от его содержания, т. е. от того, о чем будет идти в нем речь. Если выводы рассуждения, построенного в соответствии с выполнимой формулой окажутся истинными, то их истинность будет случайной, а не закономерной: при другом содержании рассуждения его выводы могут быть ложными. Иначе говоря, выполнимые формулы не гарантируют истинность выводов и, соответственно, логическую правильность тех рассуждений (независимо от их содержания), формализацией которых они являются. Поэтому, рассуждения, формой которых выступают выполнимые формулы, следует признать логически неправильными.

Читайте также:  Почему пропал канал россия 1

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

Рассмотрим следующее рассуждение: Владимир Маяковский родился в 1891 году или в 1893 году; Однако известно, что он родился не в 1891 году; Следовательно он родился в 1893 году. Формализуя это рассуждение, выделим входящие в него простые высказывания:

1. Владимир Маяковский родился в 1891 году;

2. Владимир Маяковский родился в 1893 году.

Первая часть нашего рассуждения, несомненно, представляет собой строгую дизъюнкцию этих двух простых высказываний (а ? в). Далее к этой дизъюнкции присоединяется отрицание первого простого высказывания, и получается конъюнкция ((а ? в) ? а). И наконец из этой конъюнкции вытекает утверждение второго простого суждения, и получается импликация (((а ? в) ? а) ? в), которая и является результатом формализации данного рассуждения. Теперь надо составить таблицу истинности для получившейся формулы.

Количество строк в таблице определяется по правилу 2 n , где n – количество переменных (простых высказываний) в формуле. Поскольку в нашей формуле только две переменных (а и в), то в таблице должно быть четыре строки (не считая, конечно же, верхнюю строчку, которая является так называемой «шапкой» таблицы). Количество колонок в таблице равно сумме числа переменных и числа логических союзов, входящих в формулу. В рассматриваемой формуле две переменных (а и в) и четыре логических союза (?, ?, ¬, ?), т. е. в таблице должно быть шесть колонок.

Первые две колонки представляют собой все возможные наборы истинностных значений переменных (таких наборов всего четыре: обе переменные истинны; первая переменная истинна, а вторая ложна; первая переменная ложна, а вторая истинна; обе переменные ложны).

Третья колонка – это истинностные значения строгой дизъюнкции (а ? в), которые она принимает в зависимости от всех (четырех) наборов истинностных значений переменных.

Четвертая колонка – это истинностные значения отрицания первого простого высказывания (¬а).

Пятая колонка – это истинностные значения конъюнкции, состоящей из вышеуказанной строгой дизъюнкции и отрицания ((а ? в) ? ¬а), и наконец, шестая колонка – это истинностные значения всей формулы или импликации (((а ? в) ? ¬а) ? в).

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

В четырех последних колонках таблицы представлены истинностные значения каждого из этих двучленных сложных суждений, образующих формулу. Сначала заполним третью колонку таблицы (а ? в). Для этого нам надо вернуться к предыдущему параграфу где была представлена таблица истинности сложных суждений, которая в данном случае будет для нас базисной (как таблица умножения в математике). В этой таблице мы видим, что строгая дизъюнкция ложна, когда обе ее части истинны или обе ложны; когда же одна ее часть истинна, а другая ложна, тогда строгая дизъюнкция истинна. Поэтому значения строгой дизъюнкции (а ? в) в заполняемой таблице (сверху вниз) таковы: «ложно», «истинно», «истинно», «ложно». Далее заполним четвертую колонку таблицы (¬а): когда утверждение (а) два раза истинно и два раза ложно, тогда отрицание (¬а), наоборот, два раза ложно и два раза истинно. Пятая колонка – это конъюнкция ((а ? в) ? ¬а). Зная истинностные значения строгой дизъюнкции (а ? в) и отрицания (¬а), мы можем установить истинностные значения конъюнкции, которая истинна только тогда (см. базисную таблицу в предыдущем параграфе), когда истинны все входящие в нее элементы. Строгая дизъюнкция (а ? в) и отрицание (¬а), образующие данную конъюнкцию, одновременно истинны только в одном случае, следовательно конъюнкция ((а ? в) ? ¬а) один раз принимает значение «истинно», а в остальных случаях – «ложно». Наконец, надо заполнить последнюю колонку для импликации (((а ? в) ? ¬а) ? в), которая и будет представлять истинностные значения всей формулы.

Читайте также:  Модель 1549 айфон 6

Возвращаясь к базисной таблице истинности сложных суждений, вспомним, что импликация ложна только в одном случае, когда ее основание истинно, а следствие ложно. Основанием нашей импликации является конъюнкция ((а ? в) ? ¬а), представленная в пятой колонке таблицы, а следствием является простое суждение (в), представленное во второй колонке. (Некоторое неудобство в данном случае составляет то, что слева направо следствие идет раньше основания, однако мы всегда можем мысленно поменять их местами). В первом случае (первая строчка таблицы, не считая «шапки») основание импликации ложно, а следствие истинно, значит, импликация истинна. Во втором случае и основание, и следствие ложны, значит импликация истинна. В третьем случае и основание, и следствие истинны, значит импликация истинна. В четвертом случае, как и во втором, и основание, и следствие ложны, значит импликация истинна.

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

Рассмотрим еще один пример. Требуется формализовать следующее рассуждение и установить, к какому виду относится выражающая его формула: Если какое-либо здание является старым, то оно нуждается в капитальном ремонте; Это здание нуждается в капитальном ремонте; Следовательно это здание старое. Выделим простые высказывания, входящие в это рассуждение:

1. Какое-либо здание является старым;

2. Какое-либо здание нуждается в капитальном ремонте.

Первая часть рассуждения представляет собой импликацию (а ? в) этих простых высказываний (первое является ее основанием, а второе – следствием). Далее, к этой импликации присоединяется утверждение второго простого высказывания, и получается конъюнкция ((а ? в) ? в). И наконец, из этой конъюнкции вытекает утверждение первого простого высказывания, и получается новая импликация (((а ? в) ? в) ? а), которая и является результатом формализации рассматриваемого рассуждения. Чтобы определить вид получившейся формулы, составим таблицу ее истинности. В формуле две переменных (а и в), значит в таблице будет четыре строчки (не считая верхней); также в формуле три союза (?, ?, ?), значит в таблице будет пять колонок. Первые две колонки – это истинностные значения переменных. Третья колонка – истинностные значения импликации (а g в). Четвертая колонка – истинностные значения конъюнкции ((а ? в) ? в). Пятая, последняя колонка – истинностные значения всей формулы – итоговой импликации (((а ? в) ? в) ? а). Таким образом, мы разбили формулу на три составные части, представляющие собой двучленные сложные суждения. Заполним последовательно три последних колонки таблицы по тому же принципу, что и в предыдущем примере, т. е. опираясь на базисную таблицу истинности сложных суждений.

Читайте также:  Режиссер мультфильма труп невесты

Как видим, рассматриваемая формула принимает как значение «истинно», так и значение «ложно» при различных наборах истинностных значений входящих в нее переменных, следовательно, она является выполнимой или нейтральной, а рассуждение, формализацией которого она выступает, логически неверно, или неправильно: при ином содержании рассуждения такая форма его построения могла бы привести к ошибке. (Например: Если слово стоит в начале предложения, то оно пишется с большой буквы; Слово «Москва» всегда пишется с большой буквы; Следовательно, слово «Москва» всегда стоит в начале предложения).

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

2. одна истинна, другая ложна;

3. одна ложна, другая истинна;

В этом случае заполнить первые две колонки таблицы истинности очень просто. Но как это сделать, если в формулу будут входить три переменных и количество строчек в таблице истинности для такой формулы будет равно 2 3 = 8, или если переменных будет четыре, а строчек в таблице, соответственно, – 16 и т. д.? Чтобы ответить на этот вопрос, посмотрим как заполняются первые две колонки в таблице с четырьмя строчками: в первой колонке два раза пишется «истинно», а потом два раза «ложно»; во второй колонке пишется один раз «истинно», один раз «ложно», потом опять «истинно» и еще раз «ложно». По тому же принципу заполняются первые колонки таблиц для формул с большим числом переменных и, соответственно, с большим количеством строчек в таблицах. Например, если в формуле три переменных (а, в, с), а в таблице 8 строчек, то первые три колонки, представляющие все комбинации истинностных значений переменных, заполняются так. В первой колонке четыре раза пишем «истинно», а потом четыре раза – «ложно»; во второй колонке два раза пишем «истинно», и два раза «ложно», после чего повторяем это; в третьей колонке один раз пишем «истинно», один раз «ложно» и т. д. до конца колонки.

Если в формуле четыре переменных, и в таблице ее истинности 16 строчек, то первые четыре колонки заполняются так:

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

Отрицание тождественно истинной формулы будет, очевидно, тождественно ложной формулой, и обратно.

1) все аксиомы суть тождественно истинные формулы, 2) применяя к тождественно истинным формулам правила вывода, мы получаем также тождественно истинные формулы. Отсюда следует, что все выводимые формулы исчисления высказываний, рассматриваемые как формулы алгебры высказываний, являются тождественно истинными.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock detector