СЛЕДВАНЕ НА ЕДНА ФОРМУЛА ОТ ДРУГА. ЕКВИВАЛЕНТНИ ФОРМУЛИ

    Нека j и y са формули. Ще казваме, че от j следва y, и ще пишем jy, ако всяка конфигурация, която удовлетворява j, удовлетворява и y. Ще казваме, че j е еквивалентна на y, и ще пишем jy, ако конфигурациите, които удовлетворяват j, и конфигурациите, които удовлетворяват y, са едни и същи. Очевидно условието jy е равносилно с това да бъдат едновременно изпълнени условията jy и yj.

    Пример 1. За всеки две формули j₁ и j₂ имаме съотношенията

j₁&j₂j₁, j₁&j₂j₂, j₁j₁Ъj₂, j₂j₁Ъj₂,

    Пример 2. За всеки три формули j₁, j₂, q, ако qj₁ и qj₂, то qj₁&j₂, а ако j₁q и j₂q, то j₁Ъj₂q.

    Лесно се съобразява, че jy точно тогава, когато за всяка конфигурация (S,v) е в сила неравенството j^S,vЈy^S,v, а jy точно тогава, когато за всяка конфигурация (S,v) имаме равенството j^S,v=y^S,v. Това показва, че въведените две понятия са свързани по следния начин с операциите импликация и еквиваленция: jy точно тогава, когато импликацията j®y е тъждествено вярна, а jy точно тогава, когато е тъждествено вярна еквиваленцията j«y.

    Налице са следните лесно проверими свойства на отношението следване, където j, y, q, j₁, j₂, y₁, y₂ са произволни формули, а x е произволна променлива:
    а) jj;
    б) ако jy и yq, то jq;
    в) ако jy, то ШyШj;
    г) ако j₁y₁ и j₂y₂, то j₁&j₂y₁&y₂ и j₁Ъj₂y₁Ъy₂;
    д) ако jy, то "xj"xy и $xj$xy.
От тези свойства и от отбелязаната връзка между следване и еквивалентност веднага получаваме подобни свойства на отношението еквивалентност:
    аў) jj;
    бў) ако jy и yq, то jq;
    вў) ако jy, то ШyШj;
    гў) ако j₁y₁ и j₂y₂, то j₁&j₂y₁&y₂ и j₁Ъj₂y₁Ъy₂;
    дў) ако jy, то "xj"xy и $xj$xy.
Разбира се от връзката между следване и еквивалентност непосредствено се вижда, че отношението еквивалентност е и симетрично: ако jy, то yj.

    Следните еквивалентности са в сила при всеки избор на формулите j, y, q и на променливата x (проверката може да се извърши, като се покаже, че за всяка от еквивалентностите формулата отляво и формулата отдясно имат равни стойности във всяка конфигурация):

j&jj,  jЪjj,

j&yy&j,  jЪyyЪj,

(j&y)&qj&(y&q),  (jЪy)ЪqjЪ(yЪq),

(jЪy)&q(j&q)Ъ(y&q),  (j&y)Ъq(jЪq)&(yЪq),

(jЪy)&jj,  (j&y)Ъjj,

ШШjj,  Ш(j&y)ШjЪШy,  Ш(jЪy)Шj&Шy,  Ш"xj$xШj,  Ш$xj"xШj.

Последно изменение: 26.07.1999 г.