А. Съждителни формули (изрази в алгебрата на съжденията)
При две дадени произволни съждения с помощта на операциите,
можем да образуваме съставни съждения, които също са съждения. Това
означава, че съставните съждения, евентуално оградени в скоби, могат да
участват като аргументи на операции за образуване на други съставни
съждения.
Примери за съставни съждения:
1
2.
3.
Най-общо за изразите в съждителното смятане може да се каже, че:
а) Константите 0 и 1 са изрази в съждителното смятане.
б) Съждителните променливи са изрази в съждително смятане.
в) Ако А и В са изрази в съждителното смятане, то:
• е също израз в съждителното смятане;
• e също израз в съждителното смятане;
• е също израз в съждителното смятане;
• е също израз в съждителното смятане;
• e също израз в съждителното смятане;
• e също израз в съждителното смятане
г) Ако А е е израз в съждителното смятане, то (A) е също израз в съждителното смятане.
Скобите употребяваме, за да е ясен редът, по който сме построили съответната съждителна формула.
Отрицанието е с най-висок приоритет, а конюнкцията е с по-висок приоритет от дизюнкцията, т.е. при пресмятане на вярностната стойност най-напред се пресмята отрицанието, после конюнкцията, а най-накрая дизюнкцията.
Основната задача на съждителното смятане е пресмятането на вярностната стойност на произволен израз.
Да се пресметне стойността на един израз, означава да се замести всяка съждителна променлива със съответната й стойност, а след това да се изпълнят операциите в израза.
и
Ако съждителните променливи в един израз са две, то всевъзможните двойки стойности, които тези две променливи могат да имат, са 4, т.е. 22: (0,0), (0,1), (1,0) и (1,1). Ако броят на съждителните променливи е три, то броят на всичките възможни тройки от стойности е вече 8, т.е. 23.
Ако E(p,q) e израз, в който участват съждителните променливи
p и q, на всяка двойка от стойности (p,q) на израза Е(p,q) може се съпостави съответната стойност. Така се получава таблица от стойности на израза, наричана често верностна таблица.
Таблицата показва как по зададена съждителна формула пресмятаме вярностната и стойност в зависимост от вярностните стойности на участващите съждения.
В случая със събиране на цели числа в позиционна бройна система
с основа р ще трябва да проверим верността на съждителната
форула 
за да отчетем наличието на пренос.
За някои често срещани съждителни формули при сравняване на
числа се използват специални обозначения, които се възприемат
като нови операции за сравнение. Например
се записва като
≤
(по-малко или равно), ≥
като
(по-голямо или равно), а
≠ като
(не равно).
Вярностните стойности на съкратено записаните съждения се определят по очевиден начин от таблицата на дизюнкцията.
Стойностите на логическите изрази зависят, т.е. са функции от участващите в тях логически променливи. И стойностите на променливите, и стойностите на функциите са само две – истина или лъжа, които се означават с 1 и 0. Затова се казва, че логическите функции са двоични функции на двоични променливи (аргументи).
Комбинациите от вярностни стойности на участващите в една формула съждения Х1, Х2, ..., Хn можем да разглеждаме като думи с дължина n, в които участват само 0 и 1, което множество означаваме с {0,1}n . За всяка такава дума формулата определя еднозначно верностна стойност от множеството {0,1}. С други думи, всяка съждителна формула определя функция с дефиниционна област {0,1}n и област на стойностите {0,1}.
Такава функция наричаме булева функция на n променливи.
Операциите конюнкция, дизюнкция и отрицание, с които построяваме съждителни формули, определят булеви функции със същите имена, показани в таблиците:
Изборът на операциите конюнкция, дизюнкция и отрицание за построяване на съждителни формули не е случаен. Той е обусловен от следния важен математически резултат на английския математик Джордж Бул.
Теорема. Всяка булева функция може да се представи със съждителна формула (с помощта на конюнкция, дизюнкция и отрицание).
Пример.
Нека в някакъв завод има три машини и два източника на енергия. Първият източник може да захрани кои да са две машини, а вторият – само една от тях. Да означим съответно с А, B и C съжденията: “Първата машина работи”, “Втората машина работи”, “Третата машина работи”. Задачата е да построим съждителни формули от тези три съждения за сложните условия:
F – необходимо е пускането на мощния източник.
G – необходимо е пускането на слабия източник.
Съставяме таблица за булевите функции F и G.
Описаната процедура дава следните две съждителни формули за така избраните булеви функции:
Функциите за F и G отразяват следните условия:
а/ включеният източник или източници да осигурят енергия за работещите машини;
б/ да няма излишно включени източници.
Ако в таблицата на една булева функция Е няма нито една стойност истина, тогава могат да съществуват различни съждителни формули за едно и също сложно условие (т.е. за една и съща булева функция).
Всяка съждителна формула определя функция с дефиниционна област
Б. Преобразувания на съждителни формули
1. Еквивалентност на съждителни формули
Два израза (съждителни формули) се наричат равни (еквивалентни), ако имат равни верностни стойности за всички възможни стойности на участващите в тях съждителни променливи.
Две съждителни формули са еквивалентни, ако им съответства една и съща булева функция. В такъв случай поставяме знака за равенство между такива две формули.
Ако А и В са два равни израза, тогава това записваме по следния начин: А=B.
Примери на еквиваленти изрази:
2. Начини за доказване еквивалентността на съждителни формули
а) чрез построяване на верностните таблици
В езиците за програмиране съждителните константи, променливи и изрази се наричат съответно логически или още булеви константи, логически (булеви) променливи и логически (булеви) изрази.
б) чрез свойствата на логически функции
Свойства на константите
Идемпотентни (запазващи) свойства
Свойства на отрицанието
Комутативни (разместителни свойства)
Асоциативни (съдружителни) свойства
Дистрибутивни (разпределителни) свойства
Свойства на Де Морган
Тези свойства са наречени на името на английския математик Август де Морган (1806-1871), който първи е посочил тяхното значение.
За пример да докажем асоциативното свойство
Както се вижда от двете страни на тъждеството съответства една и съща булева функция, което доказва верността му.
Докажете тъждествата (законите на Де Морган), като проверите истинността им за четирите възможни комбинации от стойности на p и q.
Образуване на съждения-отрицания с използване на законите на Де Морган
1. Да се образува съждение, противоположно на “Днес е слънчево и обичам информатика”.
По закона на Де Морган съждението-отрицание на даденото е: “Днес не е слънчево или не обичам информатика.”
2. За получаването на отрицание на съждение p=”Ще умра или ще победя” прилагаме единия от законите на Де Морган и получаваме: “Няма да умра и няма да победя”.
Всяко от горните свойства лесно се доказва, като се провери дали е изпълнено за всяка възможна комбинация от стойности на логическите променливи, участващи в него.Образуваме таблица, в която ще пресмятаме лявата и дясната страна на равенството за всяка комбинация от стойности на съждителните променливи.
Еквивалентността на две съждителни формули може да се докаже чрез еквивалентни преобразувания (с прилагане на свойствата)
Ако се доказва някое от поглъщанията, на първа стъпка A се заменя с A^1, прилагайки едно от свойствата на константите.
Много важен факт в двоичната логика е фактът, че всички възможни двоични функции, независимо от това колко е броят на аргументите им, могат да се представят като логически изрази, в които участват само трите логически операции – едноаргументната ¬ (НЕ), и двете двуаргументни ^ (И) и V (ИЛИ).
- слепване на конюнкцията
- поглъщане на дизюнкцията