Добрый вечер, господа!
Я, признаться, не особо слежу за этим блогом и допускаю, что такая тема уже поднималась. Если поднималась, прошу, ткните носом, пожалуйста.
Тем не менее, разговор у меня про алгебру логики.
Некоторое время назад попала мне в руки (ну как в руки, скажем так — на жесткий диск) отличная книжка \»Алгебра логики в задачах\» С. Г. Гиндикин.
И всё, вроде бы, логически в ней понятно, но застрял я в первом же параграфе. Вот не могу двигаться дальше, пока полностью не пойму, как это так.
Речь идёт о задаче 1.3 на странице 20. Условие в ней следующее:
(отрицание высказываний я буду обозначать, как!А и!В)
Показать, что логические связки!В–>!А; (А&!В)–>!А; (А&!В)–>В; (А&!В)–>Л, где Л — фиксированное абсолютно ложное высказывание, имеют ту же истинную таблицу, что и импликация А–>В.
Внутри я приложу объяснение решения этой задачи. Но проблема в том, что это объяснение не вполне понятно. Надеюсь, что кто–то сможет дать более понятное объяснение.
loading...
В силу этой задачи вместо доказательства абсолютной истинности А–>В можно доказать абсолютную истинность одного из четырёх перечисленных высказываний. Возьмём, например, импликацию В–>!А. Нужно в предположении истинности!В доказать истинность!А. Но это простейший способ доказательства от противного теоремы А–>В. Мы предполагаем противное тому, что требуется доказать, и получаем противоречие с тем, что дано. При доказательстве при помощи остальных трёх связок мы предполагаем не только противное тому, что требуется доказать, но и также то, что дано (А&!В). Тогда для доказательства теоремы А–>В достаточно или прийти к противоречию с тем, что дано (!А), или вывести то, что требуется доказать (В), или, наконец, получить любое абсолютно ложное высказывание (Л). В качестве последнего в силу задачи 1.2 достаточно вывести какое–нибудь высказывание С и его отрицание!С, так как тогда должно быть истинным высказывание С &!С. Последний способ доказательства является в некотором смысле наиболее общим способом доказательства от противного.
Ха, я тоже в книгах по математике всегда застреваю на первом параграфе.
Ничего сложного. Речь идет о таблице истинности, просто авторам нужно было объяснить как её строить.
Выписываются все переменные (A, B) в заглавия первых столбцов.
Далее выписываем 2^n битовых векторов в строки (n — поличество переменных).
По порядку разбираем выражения на более маленькие и считаем их значения (если можем, если не можем — разбиваем дальше, вплоть до наших «аксиом»). Затем группируем обратно и считаем опять.
Получаем красненькие столбцы «имеют ту же истинную таблицу, что и импликация А–>В» — зелененький столбец.
на рисунке я здесь забыл одно высказывание посчитать и зеленый столбец вписал в самом конце (просто места не было на листе).
не, ну с таблицами истинности всё понятно и так.
из объяснения решения я так понял, что можно как–то решить без построения таблиц. или я неправильно понял?
Да, можно. Ключевые слова: кванторы, тавтологии, подстановки, логика предикатов, исчисление предикатов, доказательство формул.
я хотел бы услышать (прочитать) объяснение этой задачки, как дано в учебнике, но с некоторыми пояснениями.
т.е. так же, но понятнее