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

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

Новые блоги и статьи Все статьи Все блоги /
Работа с объемным DOM в javascript Htext 04.04.2025 Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .	Оптимизация производительности Node.js с помощью кластеризации run.dev 04.04.2025 Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .	Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .	Пакет Context в Golang: Управление потоками и ресурсами golander 04.04.2025 Работа с горутинами в Go часто напоминает управление непослушными детьми - они разбегаются кто куда, делают что хотят и не всегда завершаются вовремя. К счастью, в Go 1. 7 появился пакет context,. . .
Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .	Свой попап в SwiftUI mobDevWorks 03.04.2025 SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .	Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .

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

	Доказательство теоремы. Исчисление высказываний 08.03.2016, 20:39. Показов 1030. Ответов 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