12,080
edits
Changes
→Logical Equivalence Problem: format
QED
QED
===Discussion===
===Discussion===
* Show that <math>\lnot (p \Leftrightarrow q)</math> is equivalent to <math>(\lnot q) \Leftrightarrow p.</math>
* Show that <math>\lnot (p \Leftrightarrow q)</math> is equivalent to <math>(\lnot q) \Leftrightarrow p.</math>
We can translate this into logical graphs by supposing that we have to express everything in terms of negation and conjunction, using parentheses for negation — that is, "(x)" for "not x" — and simple concatenation for conjunction — "xyz" or "x y z" for "x and y and z".
We can translate this into logical graphs by supposing that we have to express everything in terms of negation and conjunction, using parentheses for negation — that is, "(''x'')" for "not ''x''" — and simple concatenation for conjunction — "''xyz''" or "''x y z''" for "''x'' and ''y'' and ''z''".
In this form of representation, for historical reasons called the "existential interpretation" of logical graphs, we have the following expressions for basic logical operations:
In this form of representation, for historical reasons called the "existential interpretation" of logical graphs, we have the following expressions for basic logical operations:
The disjunction "x or y" is written "((x)(y))".
The disjunction "''x'' or ''y''" is written "((''x'')(''y''))".
This corresponds to the logical graph:
This corresponds to the logical graph:
</pre>
</pre>
The disjunction "x or y or z" is written "((x)(y)(z))".
The disjunction "''x'' or ''y'' or ''z''" is written "((''x'')(''y'')(''z''))".
This corresponds to the logical graph:
This corresponds to the logical graph:
Etc.
Etc.
The implication "x => y" is written "(x (y)), which can be read "not x without y" if that helps to remember the form of expression.
The implication "''x'' ⇒ ''y''" is written "(''x'' (''y'')), which can be read "not ''x'' without ''y''" if that helps to remember the form of expression.
This corresponds to the logical graph:
This corresponds to the logical graph:
</pre>
</pre>
Thus, the equivalence "x <=> y" has to be written somewhat inefficiently as a conjunction of to and fro implications: "(x (y))(y (x))".
Thus, the equivalence "''x'' ⇔ ''y''" has to be written somewhat inefficiently as a conjunction of to and fro implications: "(''x'' (''y''))(''y'' (''x''))".
This corresponds to the logical graph:
This corresponds to the logical graph: