Метод - истинностная таблица
Cтраница 1
Метод истинностных таблиц является хорошо известной эффективной процедурой для решения вопроса об общезначимости произвольного предложения пропозиционального исчисления. [1]
Методом истинностных таблиц гипотеза легко подтверждается. [2]
Алгоритм этого дается методом истинностных таблиц, хорошо знакомым многим читателям. [3]
Теорема 3.1 может быть доказана методом истинностных таблиц. Несложная проверка предоставляется читателю. [4]
Теорема 3 1 может быть доказана методом истинностных таблиц. Несложная проверка предоставляется читателю. [5]
Этот метод проверки истинности или ложности составных предложений называется методом истинностных таблиц. [6]
 |
Истинностная таблица для ( Р - Q / - Q / P. [7] |
Опять, как и в методе 2, мы можем использовать метод истинностных таблиц, чтобы показать, что ( Р - Q) / - Q Л Р ложна в каждой интерпретации. [8]
Исследование булева многочлена ад является не чем иным, как описанным в § 5 методом истинностных таблиц. [9]
Часто говорят, например, что разрешающая процедура Тар-ского для теории первого порядка действительных чисел [9] сложнее, чем метод истинностных таблиц для исчисления высказываний. После того как мы покажем, что классы ( / %) образуют подразбиение элементарных множеств, мы сможем уточнить это утверждение. [10]
В случае пропозиционального исчисления у нас есть простой способ проверки, является ли данная формула пропозициональ-ной тавтологией. Это описанный в V, § 5 ( см. также VII, § 2) метод истинностных таблиц. Но г случае произвольных формул исчисления & такого простого метода уже не существует. В этом параграфе мы установим теорему, утверждающую, что любой формуле а из У можно эффективно сопоставить ( с помощью некоторых простых операций над формулами) такое множество А открытых формул, что а является тавтологией в том и только в том случае, когда одна из формул множества А - тавтология. Несмотря на это, упоминаемая теорема интересна с теоретической точки зрения. Мы докажем ее в наиболее общей форме, а именно для произвольных открытых теорий. [11]
В случае пропозиционального исчисления у нас есть простой способ проверки, является ли данная формула пропозициональ-ч ной тавтологией. Это описанный в V, § 5 ( см. также VII, § 2) Метод истинностных таблиц. Но в случае произвольных формул исчисления & такого простого метода уже не существует. В этом параграфе мы установим теорему, утверждающую, что любой формуле а, из У можно эффективно сопоставить ( с помощью некоторых простых операций над формулами) такое множество А открытых формул, что а, является тавтологией в том и только в том случае, когда одна из формул множества А - тавтология. Несмотря на это, упоминаемая теорема интересна с теоретической точки зрения. Мы докажем ее в наиболее общей форме, в именно для произвольных открытых теорий. [12]
Проблема нахождения разрешающей процедуры для данного класса вопросов называется проблемой разрешения этого класса. В отличие от вопроса, является ли данная последовательность формул доказательством ( решаемого исследованием рассматриваемого конечного объекта), для ответа на вопрос, является ли данная формула теоремой, приходится производить рассмотрения, выходящие за пределы данного объекта. В силу указанных обстоятельств для формальных теорий приобретает особое значение проблема разрешения для доказуемости, которую часто и называют просто проблемой разрешения данной теории. Теория, проблема разрешения которой решается в положительную сторону, называется разрешимой, в противном случае теория называется неразрешимой. Примером разрешимой теории является исчисление высказываний: поскольку формула исчисления высказываний является теоремой тогда и только тогда, когда она - тавтология, метод истинностных таблиц дает эффективную процедуру разрешения. [13]
Логические исследования самого Буля привели к понятию, которое мы теперь называем булевой алгеброй. Фундаментальная теорема Стоуна о представлениях булевых алгебр дает возможность широких приложений теории булевых алгебр к метаматематике. Метод рассмотрения множества формул или множества классов эквивалентности формул как универсальных алгебр, предложенный Липденбаумом и Тарским, оказался важным орудием исследований. Он устанавливает связь между метаматематикой теорий, основанных на классической логике, и теорией булевых алгебр. Работы Стоуна и Тарского о взаимоотношении между интуиционистской логикой и импликативньши решетками, а также дальнейшие работы Мак-Кинси и Тарского о методах теории решеток в интуиционистском и модальном пропозициональных исчислениях установили аналогичную связь для метаматематики соответствующих неклассических теорий. Большое значение имеет здесь также и другой подход к исследованиям: интерпретация формул пропозициональных исчислений как отображений в некоторых решетках. Эта интерпретация является обобщением давно уже используемого в логике метода истинностных таблиц. Распространение этого метода на интуиционистское предикатное исчисление впервые было предложено Мостовским в связи с проблемами невыводимости формул. [14]
Страницы: 1