Тема 5. Эгалитарная логика

или логика предикатов с равенством, т.е. с двухместным предикатным символом g²_0, который интерпретируется как знак равенства. Т.о. в эгалитарной логике предикат g²₀(a, b) выражает то, что мы привыкли выражать в виде a = b и понимать как констатацию того, что объекты с обозначениями a, b являются одинаковыми, равными, неотличимыми, идентичными. Эгалитарной интерпретацией формального языка называется такая, в которой g  интерпретируется как знак равенства. Запись p₁, …, p_n│=q_{1, …}, q_m означает, что каждое из высказываний q_{1, …}, q_m является логическим следствием из высказываний p₁, …, p_n т.е. что оно является истинным в любой эгалитарной интерпретации, в которой оказываются истинными p₁, …, p_n. Высказывание p называется логически истинным, если │=p т.е. если p является истинным в любой эгалитарной интерпретации.

Правилами тождества, равенства, неотличимости называются следующие три правила соответственно:

Dg (x, x)

Dg (x_1, y₁)Ù…Ù g (x_n, y_n)Þg (f(x_1, …, x_n), f(y_1, …, y_n))

Dg² (x_1, y₁)Ù…Ù g (x_n, y_n)Þ(g f(x_1, …, x_n)Þ(y_1, …, y_n))

Теорема об эгалитарной замене: пусть  q есть результат замены в p некоторых вхождений терма a термом b; тогда если выражение g²₀(a, b) является истинным, то p равносильно q.

Теорема о транзитивности логического следствия: если p₁, …, p_n│=q₁, _…, q_m        и q₁, …, q_m│= r_{1, …}, r_e, то p₁, …, p_n│= r_{1, …}, r_e.

Теорема о расширении списка гипотез: если p₁, …, p_n│= q, то p₀, …, p_n│= q.

Теорема дедукции: если высказывания p₁, …, p_n являются замкнутыми, то p₁, …, p_n│= p тогда и только тогда когда ê= p₁Ù…Ù p_nÞp.

Теорема о конъюнктивизации гипотез: p₁, …, p_n│= p тттк p₁Ù…Ùp_n│= p.

Теорема о выводе в эгалитарной логике: правила тавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения, тождества, равенства, неотличимости образуют достаточный набор правил вывода в эгалитарной логике, т.е. p₁, …, p_n│= p тттк p может быть получено из p₁, …, p_n с помощью этого набора правил.

Теорема о сравнительной силе выводов. Если p является тавтологическим следствием из p₁, …, p_n, то p является кванторологическим следствием из p₁, …, p_n. Если p является кванторологическим следствием из р₁,…,р_n, то p является логическим следствием из р₁,…,р_n.

Алгоритм – это…

Теорема о неразрешимости проблемы логического следствия (логической истинности): нельзя придумать алгоритм, который для любых высказываний p₀, …, p_n позволял бы разрешить вопрос о том, является или нет p₀ логическим следствием из p₁, …, p_n. Полезно обратить внимание на то, что проблема тавтологического следствия является разрешимой с помощью истинностных таблиц.

Замечание последние семь теорем не исключают случай n = 0.

Замечание если не оговорено противное, слово логика понимается как эгалитарная логика.