3 dowody z logiki

[pocraka]

1. Udowodnić, że formuła zbudowana ze zmiennych zdaniowych wyłącznie za pomocą spójnika zdaniowego \(\displaystyle{ \Leftrightarrow}\) jest tautologią wtedy i tylko wtedy gdy każda zmienna występuje w niej parzystą ilość razy.
2. Udowodnić że każda formuła \(\displaystyle{ \alpha}\) znajdująca się w alternatywno - koniunkcyjnej postaci normalnej, jest równoważna formule \(\displaystyle{ \beta}\), która również znajduje się w alternatywno - koniunkcyjnej postaci normalnej.
3. Załóżmy że wyrażenie \(\displaystyle{ B}\) zawiera jedynie spójniki \(\displaystyle{ \wedge i \vee}\). Niech \(\displaystyle{ B{d}}\) oznacza wyrażenie powstające z \(\displaystyle{ B{}}\) przez zastąpienie każdego symbolu \(\displaystyle{ \vee}\) przez \(\displaystyle{ \wedge}\) zaś \(\displaystyle{ \wedge}\) przez \(\displaystyle{ \vee}\). Z kolei niech \(\displaystyle{ B{*}}\) oznacza formułe, w której każdą zmienną zastępujemy jej negacją Udowodnić że \(\displaystyle{ \neg B{d} \Leftrightarrow B{*}}\)
Z góry dziękuję za pomoc.

[welovelife]

1. Indukcja, którą rozbijasz na dwie części.

a) Zakładasz, że dla \(\displaystyle{ 2n}\) zmiennych zdaniowych \(\displaystyle{ p}\) formuła zbudowana z tych zmiennych i spójnika \(\displaystyle{ \Leftrightarrow}\) jest tautologią i pokazujesz, że dla \(\displaystyle{ (2n + 2)}\) też jest.

b) Zakładasz, że dla \(\displaystyle{ 2n-1}\) zmiennych zdaniowych \(\displaystyle{ p}\) istnieje takie wartościowanie \(\displaystyle{ \sigma (\phi) = F}\) i pokazujesz, że dla \(\displaystyle{ 2n+1}\) też istnieje takie wartościowania.

To jest bardzo proste.

2. Zadanie drugie jest błędnie sformulowane.

3. Pokazujesz z praw negowania formuł, a dokładniej z prawa negowania alternatywy i koniunkcji.