Пропозиционалдық формулалар. Тавтологиялар.

Пропозиционалдық формула ұ ғ ымы (қ ысқ аша пф) алгебралық ө рнек анық тамасына ұ қ сас.

Келесі символдар тізімінен шектелген тізбектер қ ұ растырамыз:

1) 0, 1 –– ақ иқ ат мә ндерінің символдары, оларды тұ рақ тылар деп атаймыз;

2) –– логикалық амалдар символдары (немесе пропозиционалдық байланыстар);

3) –– ә ріптердің шексіз тізімі (пропозиционалдық айнымалылар немесе жай айнымалылар);

4) (,) –– жақ шалар.

Осы шектелген тізбектердің кейбіреулерін пф деп атаймыз. Пропозиционалдық формула ұ ғ ымы индуктивті тү рде енгізіледі.

1. 0, 1 тұ рақ ты символдары пф болып табылады.

2. Ә рбір айнымалы пф болып табылады.

3-7. Егер A мен В пф болса, онда –– пф.

Анық тамада 1 жә не 2 пунктері бастапқ ы пф анық тайды, ал 3-7 пунктері жаң а пф қ ұ ру ережелері деп аталады. Мұ ндай пф { , 0, 1 } тіліндегі пф деп атаймыз.

Мысалдар. 0, 1, p, r, q, s, p₁, q₁₀ – бастапқ ы пф;

Айнымалының кез келген мә ндер жиынында тек қ ана 1 мә нін қ абылдайтын пф (сә йкес 0) тепе-тең –ақ иқ ат пропозиционалдық формула немесе тавтология (сә йкес тепе-тең -жалғ ан пропозиционалдық формула немесе қ арама-қ айшылық) деп аталады.

Кейбір негізгі тавтологияларды келтірейік. ╞ А белгілеуі А пф тавтология екенін кө рсетеді.

I. ╞ (ү шіншіні жою заң ы);

II.╞ (екі рет терістеу заң ы);

III.╞ ; IV. ╞ (идемпотенттілік заң ы);

V. ╞

VI. ╞

VII.╞ VIII. ╞ (коммутативтілік заң ы);

IX.╞ ; X. ╞ (ассоциативтілік заң ы);

XI.╞ ;

XII ╞ (дистрибутивтілік заң ы);

XIII. ╞ ;

XIV. ╞ (де Моргана заң дары);

XV. ╞ (контрапозиция заң ы);

XVI.╞ (импликацияның транзитивтілік заң ы);

XVII.╞ (жанама дә лелдеу заң ы);

XVIII.╞ (кездейсоқ тық заң ы);

XIX.╞ (эквиваленцияның транзитивтілігі заң ы);

XX ╞ (қ арама-қ айшылық заң ы);

XXI. ╞ ╞ (1 – ң жә не арқ ылы ө рнектелуі);

XXII.╞ ╞ (0 – ң

жә не арқ ылы ө рнектелуі);

XXIII.╞ ( - ң арқ ылы ө рнектелуі);

XXIV.╞ ( - ң арқ ылы ө рнектелуі);

XXV. ╞ ( - ң арқ ылы ө рнектелуі);

XXVI. ╞ ( -ң арқ ылы ө рнектелуі).