Математическая логика и теория алгоритмов

X], Xi,..., x „ соответственно буквам A], Аг,..., A „ , то так как Л есть тав­ тология, то А будет истинно, и это же значение принимает В. Таким образом, при произвольных значениях пропозициональ­ ных букв форма В принимает значение И, что и требовалось доказать. Ясно, что при подстановке в пропозициональную форму вместо пропозициональных букв высказываний, получим некоторое высказы­ вание. Высказывание, которое получается из какой-либо тавтологии посредством подстановки высказываний вместо пропозициональных букв при условии, что вхоадение одной и той же буквы замещается одним и тем же высказывайкем, называется логически истинным высказыванием. Это высказывание истинно в силу своей формы, а не в силу своего содержания. Например, высказывание: "Если Ива­ нов - студент, то Иванов - студент" всегда истинно (логически истин­ но), в то время как высказывание "Иванов - студент", если и истинно, то в силу уже других причин. Высказывание, которое можно получить с помощью подстанов­ ки в противоречие, нгяыв&ется логически ложным высказыванием. Его примером может служить высказывание: "2x2=4 и 2х2М'\ где имеет место одновременно какое-то высказывание и отрицание этого же вы­ сказывания. Пропозициональная форма называется выполнимой, если она принимает значения И хотя бы для одной совокупности значений пропозициональных букв, в нее входящих. Например, А&В является выполнимой пропозициональной фор­ мой, так как принимает значения И, когда Л=И и В=И, а форма А&\А не будет выполнимой, так как всегда ложна, Очевидно, что пропозициональная форма А выполнима тогда и только тогда, когда/1 не является противоречием, Проблема разрешимости (логики высказываний) состоит в сле­ дующем; существует ли правило, позволяющее для каждой пропози­ циональной формы А конечным числом действий выяснить, является А выполнимой или нет. 23