ЗНАЙ ИНТУИТ, Лекция, Твърдения и предикати

Компютърните науки, както беше обсъдено по-горе, изучават знакови (азбучни) системи. Алгебрата е най-адекватният математически апарат за описание на действията в тях, следователно алгебричният апарат е най-подходящ за описание на информационни системи от общ характер, абстрахирани от тяхната предметна насоченост. Информационните процеси са добре формализирани с помощта на различни алгебрични структури.

Алгебра A е определена колекция от определени елементи на X , с определени операции f, дефинирани върху тях (често определени чрез сходство с операциите събиране и умножение на числа), които отговарят на определени свойства - аксиомите на алгебрата.

Операция f се наричаn-place, ако свързва n операнда (обекти, участващи в тази операция).

Наборът от операции на алгебрата A се нарича нейна сигнатура, а наборът от елементи на алгебрата се нарича носител на алгебрата.

Изявлението (пропозиционална форма) е основна единица, неделима от гледна точка на отразяване на значението на информацията (семантика).

Твърдението е декларативно твърдение, за което може недвусмислено да се каже („като го погледнете веднага“) дали е вярно или невярно. Тези две стойности на различните предложения се обозначават като "вярно" и "невярно", "вярно" и "невярно" или "1" и "0".

Променлива, чиито стойности могат да бъдат само "1" или "0", се наричабулеваилибулева.

Пример. Помислете за фразите:

  1. Москва е столицата на САЩ.
  2. Жител на град Москва.
  3. 5 - 7 + 8.
  4. 5 - 9 + 28 = 4.
  5. Беше много студено през петата седмица на зимата.
  6. Тигрите живеят в Антарктика.

Твърдението трябва да е недвусмислено вярно илие недвусмислено невярно, следователно само твърдения 1), 4), 6) са твърдения.

Пример. Не е и твърдението за „парадокса на лъжеца“ (Евбулид, учител на Демостен, около 350 г. пр. н. е.):„Това, което сега твърдя, е невярно“, защото ако е вярно, значи е невярно и ако приемем, че е невярно, тогава е вярно. Това е неопределена пропозиционална форма. Подобен пример принадлежи на известния математик, логик Гьодел (1931):„Изложеното в това изречение не може да бъде доказано“. Ако може да се опровергае, значи не може да се докаже, а ако не може да се опровергае, значи може да се докаже. Съждения от този вид не могат да бъдат доказани или опровергани в границите на езика (тази теория, алгебра), на който са формулирани. Известни са много подобни парадокси.

Когато разглеждаме твърденията, ние не обръщаме внимание на тяхната вътрешна структура и можем да ги разложим на структурни части, както и да ги комбинираме.

Пример. Нека изградим съставни, сложни изявления от дадените прости изявления, които приемат стойността "true", ​​"false":

  1. "Зимата е студеният сезон."
  2. "Палто - топли дрехи."
  3. "Камината е източник на топлина."

Предикатът е пропозиционална форма с логически променливи (наборът от стойности на тези променливи е напълно дефиниран), което има смисъл за всякакви допустими стойности на тези променливи. Броят на променливите в предикатния запис се нарича неговолокация.

Простите твърдения или предикати не зависят от други твърдения или предикати („те не могат да бъдат разбити на по-прости“), докато сложните зависят от поне две прости.

Пример. Изразът "x = y" е предикатът, "x > 5" е предикатът и "7 > 5" е предложението. „Добро“ твърдениене е твърдение, твърдението „Оценката на студент А по информатика е добра“ е просто твърдение, твърдението „Вчера времето беше ясно, вчера ходих на риболов“ е съставно твърдение, състоящо се от две прости.

Логическата (булева) функция f(x) е определена функционална зависимост, в която аргументът x е логическа променлива с даден набор от промени на аргумента, а стойностите на функцията f(x) се вземат от двуелементния набор R(f) = .

Пример. Дадени са предикати от формата p = „числото x се дели на 3“ и q = „y е денят от седмицата“. Намерете истинското множество от предикати р и q, ако , . Получаваме това, .

Набор от логически променливи соперации, дефинирани над него: -отрицаниеилиинверсия, -логическо добавянеили дизюнкция, -логическо умножениеили конюнкция се нарича алгебра на предикатите (и предложенията), ако тези операции удовлетворяват следните аксиоми:

Аксиома за двойно отрицание:

Аксиоми за транспортируемост на операнд (относно операции на дизюнкция и конюнкция):

Аксиоми за транспортируемост на дизюнкция и конюнкция (по отношение на операндите):

Аксиоми за еднакви операнди:

Аксиоми за усвояване (чрез множител - множител-сума или член - член-продукт):

Аксиоми за разпределение на операции (дизюнкции по отношение на конюнкции и обратно):

Аксиоми на Де Морган (прехвърляне на двоична операция към операнди):

Аксиоми на неутралност (взаимно обратни фактори или термини):

Аксиомата за съществуването на единица (вярно, вярно, 1) и нула (лъжа, невярно, 0), освен това,

От тези аксиоми следват редица полезни отношения, напр.