Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

529 users

0 votes
How can I proof SAT or VALID for a given boolean formular? And is this relevant for exam?

I tried to process exercise 4 b) of the exam WS17 but I couldn't find how this exactly works in the presentation of lecture DiRa-04-PropLogic-1. In the solution is just written "TAUTOLOGY".

Thanks to all the answerers.

Best regards,

Nick Jochum
in # Mandatory Modules Bachelor by (1.1k points)

1 Answer

+1 vote
 
Best answer

What about this solution:

    ((¬a ∨ a) ↔ (b ∨ a)) → (¬((¬a ∨ b) ∧ a) ↔ a ⊕ b)
    = (1 ↔ (b ∨ a)) → (¬((¬a ∨ b) ∧ a) ↔ a ⊕ b)
    = (b ∨ a) → ((¬((¬a ∨ b) ∧ a) ↔ a) ⊕ b)
    = (b ∨ a) → ((¬((¬a ∨ b) ∧ a) ∧ a ∨ ((¬a ∨ b) ∧ a) ∧ ¬a) ⊕ b)
    = (b ∨ a) → ((¬((¬1 ∨ b) ∧ 1) ∧ a ∨ ((¬0 ∨ b) ∧ 0) ∧ ¬a) ⊕ b)
    = (b ∨ a) → ((¬b ∧ a) ⊕ b)
    = (b ∨ a) → ((¬b ∧ a) ∧ ¬b ∨ ¬(¬b ∧ a) ∧ b)
    = (b ∨ a) → ((1 ∧ a) ∧ ¬b ∨ ¬(¬1 ∧ a) ∧ b)
    = (b ∨ a) → (a ∧ ¬b ∨ ¬0 ∧ b)
    = (b ∨ a) → (a ∧ ¬b ∨ b)
    = (b ∨ a) → (a ∨ b)
    = ¬(b ∨ a) ∨ (a ∨ b)
    = ¬(a ∨ b) ∨ (a ∨ b)
    = 1

 

by (166k points)
selected by

Related questions

0 votes
1 answer
+3 votes
1 answer
+1 vote
1 answer
+1 vote
1 answer
asked Aug 23, 2020 in # Mandatory Modules Bachelor by least (260 points)
0 votes
1 answer
asked Aug 23, 2020 in # Mandatory Modules Bachelor by VF (120 points)
Imprint | Privacy Policy
...