- Tytuł:
-
An algorithm for solving the tautology problem
O pewnym algorytmie badania tautologii rachunku zdań - Autorzy:
- Karbowska, J.
- Powiązania:
- https://bibliotekanauki.pl/articles/341147.pdf
- Data publikacji:
- 2002
- Wydawca:
- Politechnika Białostocka. Oficyna Wydawnicza Politechniki Białostockiej
- Tematy:
-
metoda rozstrzygania
tautologia rachunku zdań
decidability procedure
propositional tautology - Opis:
-
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 .
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. - Źródło:
-
Zeszyty Naukowe Politechniki Białostockiej. Informatyka; 2002, Z.1; 71-81
1644-0331 - Pojawia się w:
- Zeszyty Naukowe Politechniki Białostockiej. Informatyka
- Dostawca treści:
- Biblioteka Nauki
Artykuł