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

@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{ ... }

Новые блоги и статьи Все статьи Все блоги /
Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .	Метод с двумя буферами (или double buffering) или ping-pong buffering Hrethgir 02.04.2025 Из ответов LM модели. Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .	На любовном киберфронте Alexander-7 01.04.2025 Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка: «Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .
Как работает Node.js изнутри run.dev 29.03.2025 Node. js изменил подход к разработке веб-приложений, позволив использовать JavaScript не только на стороне клиента, но и на сервере. Созданный в 2009 году Райаном Далем, этот открытый,. . .	Моки в Python: Mock Object Library py-thonny 29.03.2025 Тестирование кода требует особого подхода, когда речь идёт о компонентах, взаимодействующих с внешним миром. Мы часто сталкиваемся с непредсказуемостью HTTP-запросов, чтением данных из базы или. . .	JavaScript: Управление памятью и улучшение производительности run.dev 29.03.2025 В отличие от низкоуровневых языков программирования, JavaScript не требует ручного выделения и освобождения памяти. Здесь работает автоматический сборщик мусора, который определяет, какие объекты. . .	Мультитенантная архитектура со SpringBoot и PostgreSQL ArchitectMsa 29.03.2025 SaaS-приложения редко обслуживают одного клиента и обычно они должны поддерживать множество организаций, каждая из которых работает в своём изолированном пространстве. Мультитенантная архитектура. . .	std::span в C++: Производительность и лучшие практики NullReferenced 28.03.2025 std::span — одно из самых недооценённых нововведений стандарта C++20, которое радикально меняет подход к работе с непрерывными последовательностями данных. По сути, это невладеющее представление. . .

@Kaligulaa 6 / 7 / 2 Регистрация: 18.05.2015 Сообщений: 124

	Доказательство теоремы. Исчисление высказываний 08.03.2016, 20:39. Показов 1028. Ответов 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 $Эксперт по математике/физике$ 4302 / 2093 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	08.03.2016, 21:50
	Оформите, пожалуйста, Ваше решение более строго, чтобы мы могли проверить, правильно ли оно или нет. В нынешнем виде Ваше решение мне представляется таким: Хотим: Доказать, что пары связок не достаточно для выражения любой истинностной функции. 1. Рассмотрим конкретную функцию X одного аргумента, составленную из связок. 2. Докажем, что X не является отрицанием. 3. Сделаем вывод, что найдётся истинностная функция (я так понимаю, отрицание), что никакая функция, составленная из связок, не выражает её. Мне кажется, что пункт 3 требует обоснования. Обратите внимание на выделенные курсивом слова. Добавлено через 57 секунд P.S. отрицание в LaTeX обозначается `\neg` или `\overline{ ... }` 1