Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Противоречием {тождественно ложной пропозициональной формой) на­ зывается пропозициональная форма, принимающая значение Л при любой со­ вокупности истинностных значений букв, входящих в нее. Примеры противоречий: A<& —IA, А=—А. Очевидно, что форма А является тавтологией тогда и только тогда, когда -пЛ есть противоречие. Тавтологию будем обозначать через Т, а противоречие - через П. Сформулируем и докажем две несложные теоремы. Теорема 1.1. Если Л - тавтологии, то В - тавтология. Доказательство. Пусть А и А^В - тавтологии. Допустим, что при некото­ ром распределении истинностных значений для пропозициональных букв, вхо­ дящих ъ А В, В принимает значение Л. Поскольку А есть тавтология, то при этом распределении истинностных значений А принимает значение И. Тогда А ^ В получит значение Л. Это противоречит предположению о том, чтоА ^ В есть тавтология. Теорема доказана. Теорема 1.2. Если А есть тавтология, содержащая пропозициональные буквы ^7, А2,..., An, и В получается из А подстановкой в А пропозициональных форм Ai, А2,... А„ вместо букв Aj, А2,..., А„ соответственно, то В есть тавтоло- гия, т.е. подстановка в тавтологию приводит к тавтологии. Доказательство. Пусть задано произвольное распределение истинностных значений для пропозициональных букв, входящих в В. Формулы A i ,А 2 A n примут тогда некоторые значения xi, Х2,..., (каждое Х/ есть И или Л). Если придадим значения Xj, Х2,..., соответственно буквам ^7, А2,..., А„ , то так как Л есть тавтология, то А будет истинно, и это же значение принимает В. Таким об­ разом, при произвольных значениях пропозициональных букв форма В прини­ мает значение И, что и требовалось доказать. Пропозициональная форма называется выполнимой, если она принимает значения И хотя бы для одной совокупности значений пропозициональных букв, в нее входящих. Например, А&В является выполнимой формой, так как принимает значе­ ния И, котм А=И и В=И, а форма А&—Л не будет выполнимой, так как всегда ложна. Очевидно, что форма А выполнима тогда и только тогда, когда А не яв­ ляется противоречием. Проблема разрешимости (логики высказываний) состоит в следующем: существует ли правило, позволяющее для каждой пропозициональной формы А конечным числом действий выяснить, является А выполнимой или нет? 11