please help with full explanation. thank u Advanced Topics: Satisfiability (10 p
ID: 3749403 • Letter: P
Question
please help with full explanation. thank u
Advanced Topics: Satisfiability (10 pt.) Many problems, in diverse areas such as artificial intelligence and circuit design, can be modeled in terms of propositional satisfiability A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. For example, p ^ q is true when p T and q T; thus, p ^ q is satisfiable When no such assignment exists, the compound proposition is unsatisfiable. (4 pt., 2 pt. each) Answer each of the following questions. a. Explain why if a compound proposition is unsatisfiable, then its negation is a tautology b. Give an example of an unsatisfiable compound proposition with two variables, p and q. 6. Justify your answer.Explanation / Answer
Let us understand some terms before answering the question.
A tautology is a logic which is always true. A logic is called satisfiable when it is true for at least one true assignment of its variables. That necessarily does not mean that a satisfiable logic would always be a tautology. It may be a tautology or maybe not. But a tautology is always satisfiable.
p q p q
T T T
T F. F
F T F
F. F. F
p q p q
T T T
T F T
F T T
F. F F
Both the above statements are satisfiable because they are true, at least once for one true assignment of its variables. But clearly, they are not tautologies. However, A tautology is always true, therefore naturally it is satisfiable because at least means one or more than one. So if all results are true, then also it would be satisfiable.
Now for a logic to be unsatisfiable it should be opposite to satisfiable. Look at the definition of satisfiable carefully. It says, ‘at least one assignment’, the opposite of this is, ‘No assignment’. That means, a logic is unsatisfiable when no assignment to its variable can make it true, or it is always false. A statement which is always false, naturally its negation would always be true. And a statement which is always true is a tautology. Therefore, the negation of an unsatisfiable logic is always a tautology.
( pq) (¬p ¬q) is an unsatisfiable logic since it would always be false.
p q pq ¬p ¬q ¬p ¬q ( pq) (¬p ¬q)
T T T. F. F F F
T F T. F . T F F
F T. T. T F F F
F. F F. T T T F
The above statement is always false. Therefore, it is an unsatisfiable logic.
If I negate the compound expression, It would naturally become a tautology.
Hope it helps:)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.