An algorithm for solving the tautology problem

• Autorzy: Karbowska J.

Warianty tytułu

PL

O pewnym algorytmie badania tautologii rachunku zdań

• Języki publikacji: EN

Abstrakty

EN

In the present paper we propose an algorithm deciding, whether a given formula a is a tautology of the propositional logic. The worst case complexity of the algorithm is of the order .

PL

W pracy został przedstawiony algorytm sprawdzania czy dana formuła rachunku zdań należąca do języka , zbudowana ze zmiennych, stałej zero, nawiasów oraz znaku implikacji, jest tautologią. Idea algorytmu jest oparta na regułach transformacji. Reguły te zachowują tautologiczność formuły, tzn. formuła , która jest tautologią po zastosowaniu odpowiedniej reguły w dalszym ciągu jest tautologią. Jeśli dana formuła jest różna od stałej lub zmiennej, to w formule znajdujemy ostanie wystąpienie znaku implikacji i stosujemy odpowiednią regułę otrzymując nowy ciąg formuł. Formuły przekształcamy do momentu, kiedy otrzymamy ciąg pusty (wtedy jest ona tautologią), bądź zmienną bądź stałą. Złożoność tego algorytmu, w najgorszym przypadku, wynosi , gdzie oznacza długość formuły.

Słowa kluczowe

EN

decidability procedure; propositional tautology

PL

metoda rozstrzygania; tautologia rachunku zdań

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Zeszyty Naukowe Politechniki Białostockiej. Informatyka
• Rocznik: 2002
• Tom: Z.1
• Strony: 71--81
• Opis fizyczny: Bibliogr. 6 poz., tab.

Twórcy

autor

Karbowska J.

• Politechnika Białostocka, Katedra Informatyki Technicznej, ul. Wiejska 45 A, 15-351 Białystok

Bibliografia

• [1] A.V. Aho,J. E. Hopcroft , J. D. Ullman: Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983.
• [2] B. Monien, E.: Speckenmeyer, Solving satisfability in less than 2" steps, Discrete Appl. Math. 10 (1985), no 3, 287-295.
• [3] C. Papadimitriou: Computational Complexity, Addison — Wesley (1994).
• [4] N. Deo, J. Nievergelt, E. M. Reingold: Algorytmy kombinatoryczne, PWN, Warszawa 1985.
• [5] H. Rasiowa, R. Sikorski: The matematics of metamathemafics, PWN, Warszawa 1970.
• [6] S. Alagić, M. A. Arbib: Projektowanie programów poprawnych i dobrze zbudowanych, WNT, Warszawa 1982.