ЕКВИВАЛЕНТНИ ФОРМУЛИ
Нека F и G са формули. Ще казваме, че F е еквивалентна на G (или че F и G са еквивалентни), и ще пишем F є G, ако за всяка структура S и всяка оценка v в S на променливите е изпълнено равенството FS,v=GS,v. Очевидно условието F є G е равносилно с това да бъдат едновременно изпълнени условията F ъ= G и G ъ= F.
Пример 1. Нека F е произволна формула. Тогава всяка от формулите and(F) и or(F) е еквивалентна на F. По-общо, всяка формула, имаща вида and(F,F...,F) или вида or(F,F...,F), е еквивалентна на F.
Пример 2. При всеки избор на положително цяло число n и на формули F1, F2, ..., Fn са в сила съотношенията
| and(F1,F2...,Fn,Fn+1) | є | and(and(F1,F2...,Fn),Fn+1), |
| or(F1,F2...,Fn,Fn+1) | є | or(or(F1,F2...,Fn),Fn+1). |
Пример 3. Нека F е произволна формула, а X е променлива, която не е свободна променлива на F. Тогава всяка от формулите "X F и $X F е еквивалентна на F. В това се убеждаваме, като забележим, че за всяка структура S, всяка оценка v в S на променливите и всеки елемент x на носителя на S е в сила равенството
FS,v[X:x] = FS,v
(понеже оценките v[X:x] и v съвпадат за свободните променливи на F).
Пример 4. Нека F е произволна формула, а X и Y са две различни променливи. Тогава са в сила съотношенията
"X "Y F є "Y "X F и $X $Y F є $Y $X F. Първото от тях се доказва, като се използва, че винаги, когато S е някоя структура, D е нейният носител и v е оценка в S на променливите, имаме равенствата
("X "Y F)S,v = min{("Y F)S,v[X:x] | xОD} = min{min{FS,v[X:x][Y:y] | yОD}| xОD} = min{FS,v[X:x][Y:y] | xОD, yОD},
("Y "X F)S,v = min{("X F)S,v[Y:y] | yОD} = min{min{FS,v[Y:y][X:x] | xОD}| yОD} = min{FS,v[Y:y][X:x] | xОD, yОD},
а v[X:x][Y:y] съвпада с v[Y:y][X:x] при всеки избор на x и y в D. Второто от съотношенията се доказва по аналогичен начин.
Забележка. Пример 6 във връзка със следване на една формула от друга показва, че не при всеки избор на формулата F двете формули "X $Y F и $Y "X F са еквивалентни.
Лесно се проверяват следните свойства на отношението еквивалентност, където F, F1, ..., Fn, G, G1, ..., Gn, H са произволни формули, а X е произволна променлива:
а) F є F;
б) ако F є F, то G є F;
в) ако F є G и G є H, то F є H;
г) ако F1 є G1, F2 є G2, ..., Fn є Gn, то and(F1,F2...,Fn) є and(G1,G2...,Gn) и or(F1,F2...,Fn) є or(G1,G2...,Gn);
д) ако F є G, то ШF є ШG,
"X F є "X G и $X F є $X G;
е) Ш true є false;
ж) Ш false є true;
з) Ш and(F1,F2...,Fn) є or(ШF1,ШF2...,ШFn);
и) Ш or(F1,F2...,Fn) є and(ШF1,ШF2...,ШFn);
й) ШШF є F;
к) Ш"X F є $XШF;
л) Ш$X F є "XШF.
Например свойството к) се доказва, като се използва, че винаги, когато S е някоя структура, D е нейният носител и v е оценка в S на променливите, имаме равенствата
(Ш"X F)S,v = 1 - ("X F)S,v = 1 - min{FS,v[X:x] | xОD} = max{1 - FS,v[X:x] | xОD} = max{(ШF)S,v[X:x] | xОD} = ($XШF)S,v.
Последно изменение: 1.04.2002 г.