Доказательство теоремы. Исчисление высказываний

@Kaligulaa · Регистрация: 18.05.2015

Author24 — интернет-сервис помощи студентам

Доказать, что каждая из пар связок $https://www.cyberforum.ru/cgi-bin/latex.cgi?\rightarrow ,\vee$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv , -$ не являются достаточной для выражения любой истинностной функции
Для примера рассмотрел $https://www.cyberforum.ru/cgi-bin/latex.cgi?(A\vee A)\rightarrow A$
Составим таблицу истинности
$https://www.cyberforum.ru/cgi-bin/latex.cgi?A| \vee| \rightarrow$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?T|T|T$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?F|F|T$
Это все равно, что представить это как форму $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\vee \bar A \equiv (A\vee A)\rightarrow A$ , но ее недостаточно для выражения $https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar A$ , значит не всякую истинностную функцию можно построить с помощью данных двух связок.
Есть ли ошибки в рассуждениях? Поправьте , если что-то не так
А вот вторая задача
Интерпретируем связки следующим образом $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(A)=\bar (A \equiv A)$
Таблица
$https://www.cyberforum.ru/cgi-bin/latex.cgi?A|F(A)$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?T|F$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?F|F$
Аналогично можно рассуждать и прийти к такому выводу? Правильные ли рассуждения? и кстати почему с помощью
отрицания нельзя выразить любую истинностную функцию? Что мешает?

@Mysterious Light · 08.03.2016, 21:50

Оформите, пожалуйста, Ваше решение более строго, чтобы мы могли проверить, правильно ли оно или нет.

В нынешнем виде Ваше решение мне представляется таким:
Хотим: Доказать, что пары связок не достаточно для выражения любой истинностной функции.
1. Рассмотрим конкретную функцию X одного аргумента, составленную из связок.
2. Докажем, что X не является отрицанием.
3. Сделаем вывод, что найдётся истинностная функция (я так понимаю, отрицание), что никакая функция, составленная из связок, не выражает её.
Мне кажется, что пункт 3 требует обоснования. Обратите внимание на выделенные курсивом слова.

Добавлено через 57 секунд
P.S. отрицание в LaTeX обозначается \neg или \overline{ ... }

@Kaligulaa 6 / 7 / 2 Регистрация: 18.05.2015 Сообщений: 124
		1
	Доказательство теоремы. Исчисление высказываний 08.03.2016, 20:39. Показов 1022. Ответов 1 Метки нет (Все метки) Доказать, что каждая из пар связок $https://www.cyberforum.ru/cgi-bin/latex.cgi?\rightarrow ,\vee$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv , -$ не являются достаточной для выражения любой истинностной функции Для примера рассмотрел $https://www.cyberforum.ru/cgi-bin/latex.cgi?(A\vee A)\rightarrow A$ Составим таблицу истинности $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\| \vee\| \rightarrow$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?T\|T\|T$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?F\|F\|T$ Это все равно, что представить это как форму $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\vee \bar A \equiv (A\vee A)\rightarrow A$ , но ее недостаточно для выражения $https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar A$ , значит не всякую истинностную функцию можно построить с помощью данных двух связок. Есть ли ошибки в рассуждениях? Поправьте , если что-то не так А вот вторая задача Интерпретируем связки следующим образом $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(A)=\bar (A \equiv A)$ Таблица $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\|F(A)$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?T\|F$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?F\|F$ Аналогично можно рассуждать и прийти к такому выводу? Правильные ли рассуждения? и кстати почему с помощью отрицания нельзя выразить любую истинностную функцию? Что мешает? 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	08.03.2016, 21:50	2
	Оформите, пожалуйста, Ваше решение более строго, чтобы мы могли проверить, правильно ли оно или нет. В нынешнем виде Ваше решение мне представляется таким: Хотим: Доказать, что пары связок не достаточно для выражения любой истинностной функции. 1. Рассмотрим конкретную функцию X одного аргумента, составленную из связок. 2. Докажем, что X не является отрицанием. 3. Сделаем вывод, что найдётся истинностная функция (я так понимаю, отрицание), что никакая функция, составленная из связок, не выражает её. Мне кажется, что пункт 3 требует обоснования. Обратите внимание на выделенные курсивом слова. Добавлено через 57 секунд P.S. отрицание в LaTeX обозначается `\neg` или `\overline{ ... }` 1