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

мина в посылках различают четыре фигуры силлогизма. Модусами силлогизма называются разновидности силлогизма, отличающиеся качественной и количественной характеристикой посылок и заключе­ ния. Силлогизмам присваивают собственные имена, например, силло­ гизм A A A называется Barbara (в слове «Barbara» гласными являются три буквы а). Можно подсчитать, что количество различных модусов силлогизмов Аристотеля равно 256 (по 64 в каждой фигуре). Сколько же среди этих модусов правильных, когда из истинности посылок следует истинность заключения? Известно, что правильных моду­ сов 24. Рассмотрим применение метода резолюций для выяснения правильности модусов, Рассмотрим силлогизм Барбара, построенный по первой фигуре, В символьной записи он означает, что из истинности формул Ух{S{x)=>P(x)\ Vx (Р(х)=>б(л)) нужно получить истинность формулы \/x{Six)^Q{x)). т. е. доказать, что из формул Ух{8(х)=>Р(х)) и yx(P(x)=>Q(x)) логиче­ ски следует формула \fx{S(x)=>Q{x)). Известно, что, если формула С = (Уx(S(x)^P(x)))&iVx{P(x)^Q{x)))&^ Vx(%)=>6(x)) (3. является противоречием, из посылок силлогизма будет логически сле­ довать его заключение. Так как формула С содержит только одноме­ стные предикатные буквы {S,P,Q), то выяснение - противоречие С или нет - можно было бы свести к проблеме разрешимости логики выска­ зываний. При этом получили бы нетривиальную задачу в силу сле­ дующего. В формуле С три предикатные буквы, следовательно, нужно было бы взять множество, содержащее 2^=8 элементов, положим М ={1,2,...,8}. Тогда каждый предикат порождает на М по 8 выска­ зываний; 5(1),...,5(8); Р(1),...,Р(8); Следовательно, в пропозициональной форме, построенной для С, будет 24 переменных и таблица истинности будет содержать 2^"* строк. Ясно, что составление такой таблицы сложно даже 114