Érvényesség
Az érvényesség egy logikai képlet tulajdonsága, amely abból áll, hogy ez a formula igaz a benne foglalt nem logikai szimbólumok, azaz predikátum- és propozíciós változók bármilyen értelmezése esetén. Az ezzel a tulajdonsággal rendelkező logikai formulákat univerzálisan érvényesnek vagy azonosan igaznak vagy tautológiáknak nevezzük . Bármely általánosan érvényes formula logikai törvényt fejez ki. Az "A képlet általában érvényes" szavak helyett gyakran ezt írják: .
A logikai formulák legfontosabb típusai a propozíciós és állítmányi formulák. A logikai műveletek klasszikus felfogásában a propozíciós formulák érvényességét igazságtáblázatok készítésével ellenőrzik : egy formula akkor és csak akkor érvényes, ha a kijelentési változók bármely igazságértékére az ÉS értéket veszi fel ("igaz"). . A predikátum formula érvényessége bármely modellben igazságot jelent. Az univerzálisan érvényes predikátumképletek halmaza eldönthetetlen , vagyis nincs olyan algoritmus , amely lehetővé tenné, hogy egy tetszőleges predikátumképlet megtudja, hogy az érvényes-e (ez Church eredménye). Gödel teljességi tételéből következik, hogy a klasszikus predikátumszámításban minden érvényes predikátumképlet, és csakis azok, származtatható .
Irodalom
- Verescsagin, Shen. Előadások a matematikai logikáról és az algoritmusok elméletéről. – MTsNMO, 2002.
- Ershov Yu.L., Palyutin E.A. Matematikai logika. — M.: Nauka, Fizmatlit, 1987.
- Igoshin V.I. Matematikai logika és algoritmusok elmélete. – Akadémia, 2008.
- Klini S.K. Matematikai logika. — M.: Mir, 1973.
- Mendelson E. Bevezetés a matematikai logikába. - M. Nauka, 1971.
- Novikov P.S. A matematikai logika elemei. - M.: Nauka, 1973.