## Linux HowTo: Curious tautological pattern on“p->p”

I found something that boggles me ( I’m really a beginner in symbolic logic, so maybe it’s very trivial).

I was practicing with truth-tables, and I found that:

1. “p->p” is a tautology

2. “(p->p)->p” is not a tautology.

I decided to go further, and:

1. “((p->p)->p)->p” is again a tautology, but

4.”(((p->p)->p)->p)-> p” is not, and it keeps alternating.

I checked with an online logic calculator, and it seems correct.

Now, do you know why is that? Is there any particular reason for this pattern?

Cheers

1) For any formula $$p$$, $$p to p$$ is a tautology.
2) For any tautology $$T$$, $$T to p$$ is logically equivalent to $$p$$. (Check it out with a truth table.)

So an even amount of occurrences of $$p$$ will give you tautologies (by 1)); appending another $$p$$ will give you something that behaves like p (by 2)). And if you take that $$p$$-equivalent proposition and append another $$p$$, you will, by 1), get the tautology again, etc.

I love @lemontree’s explanation (and @Manx’s terser version of the same point). It may be useful to see the point in a different way, though:

$$(p rightarrow p) rightarrow p$$ is equivalent to $$neg (neg p lor p) lor p$$, which by one of De Morgan’s laws is equivalent to $$(neg neg p ,&, neg p) lor p$$.

That last expression is equivalent to $$(p ,&, neg p) lor p$$.

The left disjunct of that expression is a contradiction, though; it’s always false, so the truth value of the whole expression is the same as the truth value of $$p$$.

lemontree’s answer shows that you can apply this conclusion to understand the longer expressions.

For example, $$((p rightarrow p) rightarrow p) rightarrow p$$ embeds the original 3-$$p$$ expression on the left side of the arrow, and we saw that that was equivalent to $$p$$, so the whole expression is equivalent to $$p rightarrow p$$.

Tagged : /

## Math Genius: Why is a deductive closure an intersection of maximally consistent sets?

Full Question:
Show that if $$Delta(Gamma)$$ is the deductive closure of a consistent $$Gamma$$ then $$Delta(Gamma)$$ is the intersection of all maximal consistent sets of formulas $$Lambda$$ with $$Gamma subseteq Lambda$$.

I’m really stuck with this question, I honestly don’t know how to even start. Can someone please provide some assistance?

You have two things to prove: (1) that $$Delta(Gamma)$$ is a subset of any maximal consistent superset of $$Gamma$$; (2) that if $$phi notin Delta(Gamma)$$ then there is a maximal consistent superset of $$Gamma$$ that does not contain $$phi$$.

For (1), if $$chi in Delta(Gamma)$$ and $$Lambda$$ is a consistent superset of $$Gamma$$, then so is $$Lambda cup {chi}$$. So if $$Lambda$$ is a maximal consistent superset, then $$chi in Lambda$$.

For (2), use Zorn’s lemma: consider the set $$cal C$$ of all consistent supersets of $$Gamma$$ that do not contain $$phi$$. There is at least one member of $$cal C$$, namely $$Gamma$$ itself. The union of a chain of elements of $$cal C$$ is also a member of $$cal C$$, so by Zorn’s lemma $$cal C$$ has a maximal element.

Tagged : /

## Math Genius: What is the minimal disjunctive normal form of this propositional logic formula?

I have the following formula: $$(neg Aland Bland C)vee (neg Aland Bland neg C)vee (neg Aland neg B)vee (Aland C)vee (Alandneg C)$$

After I did a Karnaugh Map for this formula I found out it is a tautology (in other words – all squares in the map are filled with ones). What is the minimal disjunctive normal form of this formula then?

I’ll show you how to prove the statement is tautology without Karnaugh’s map:

$$(1)$$ distribution:
$$(neg Aland Bland C)lor (neg Aland Bland neg C)equiv(neg Aland B)land(Clorneg C)equiv(neg Aland B)$$
$$(2)$$distribution again:
$$(neg Aland B)lor(neg Alandneg B)equivneg Aland(Blorneg B)equivneg A$$
$$(3)$$distribution once again:
$$(Aland C)lor(Alandneg C)equiv Aland(Clorneg C)equiv A$$

$$underbrace{underbrace{(neg Aland Bland C)lor(neg Aland Bland neg C)}_{neg Aland B}lor(neg Aland neg B)}_{neg A}lorunderbrace{(Aland C)lor(Alandneg C)}_{A}equivneg Alor Aequiv 1$$

Tagged :

## Server Bug Fix: Negation of “Either X is true, or Y is true, but not both”

Negation of “Either X is true, or Y is true, but not both”

My attempt:

If seems that let X be true and Y be true, not X for X is false and not Y for Y is false. In order for the above statement to be True, we need:

The negation of both X and Y to be true: negate(X and Y) -> not X or not Y

For “Either X is true, or Y is true, but not both” is equivalent to below:

((X or Y) and (not X or not Y))

The negation of the above (negation turns “and” into “or”, and turns “or” into “and”):

((not X and not Y) or (X and Y))

Is this logical or? I am pretty lost…

A basic approach is to see there only are 4 possibilities:

1. $$X$$ and $$Y$$
2. $$X$$ and not $$Y$$
3. not $$X$$ and $$Y$$
4. not $$X$$ and not $$Y$$

Your statement was (2) or (3), so its negation is (1) or (4).

I give a solution by formal calculation: translate the phrase into logical symbols, we have $$text{negation}rightarrowneg$$, $$text{either X or Y is true}rightarrow Xlor Y$$, $$text{but not both}rightarrowlandneg(Xland Y)$$. Then

$$neg((Xlor Y)landneg(Xland Y)=neg(Xlor Y)lor(negneg(Xland Y))=(neg Xlandneg Y)lor(Xland Y)$$

The final result is identical to yours.

Either $$X$$ is true, or $$Y$$ but not both is

($$X$$ OR $$Y$$) AND (NOT [$$X$$ AND $$Y$$])

Now the negation of $$A$$ AND $$B$$ is:

(not A) OR (not B).

So the negation is:

[NOT (X OR Y)] OR (NOT(NOT([X AND Y]))

And NOT(NOT(A)) is .. A so

[NOT (X OR Y)] OR [X AND Y]

And the negation of A OR B is: (NOT A) AND (NOT B).

So

(NOT X AND NOT Y) OR (X AND Y)

So the negation is

Either both X and Y are true, or both X and Y are false.

Maybe that is what it intuitively what you would have thought.

Tagged : /

## Server Bug Fix: Why does \$AB + BC + CA = (Aoplus B)C + AB\$ not imply \$BC + CA = (Aoplus B)C\$ in boolean algebra?

I am new to Logical Inequalities. Please bear with me if I am inexplicably stupid.

The following is a Proven Equality:
$$AB + BC + CA = (Aoplus B)C + AB$$
I noticed that I cannot “cancel out” $$AB$$ from both sides of the identity, i.e.
$$BC + CA neq (Aoplus B)C$$

In mathematical equations, we cancel out stuff all the time. For example,
$$X + 3 = Y + 3 quadimpliesquad X = Y$$

Can this not be done with Logical Statements? Is there a reason why this is such a way?

In general, in a Boolean algebra it is not true that if equal terms appear on both sides of an equivalence, then we may “cancel” them (cancellation law). In other words,
begin{align} A+C = B + C ,not!!!implies A = B end{align}

Indeed, consider the case where $$A = 1 = C$$ and $$B = 0$$. Then, $$A + C = 1 + 1 = 1 = 0 + 1 = 1 = B$$ but $$A = 1 neq 0 = B$$.

You have the phenomenon in set theory, and essentially for the same reason. To see the analogy, consider the boolean $$+$$ (the logical “or”) as the set union $$cup$$. We have have that:
begin{align} A cup C = B cup C , not!!!implies A = B end{align}
Indeed, take $$A = {a}$$, $$B = {b}$$ and $$C = {a,b}$$, with $$a neq b$$. Then, $$A cup C = {a,b} = B cup C$$ but $$A = {a} neq {b} = B$$.

The deep reason is that boolean $$+$$, as well as set union $$cup$$, is idempotent, differently than arithmetical $$+$$ in natural numbers. Idempotence means that $$a + a = a$$ for any $$a$$ in your domain.
This is what happens with any $$a in {0,1}$$ and boolean $$+$$, as well as with any set and set union $$cup$$.
Idempotence makes impossible to define a “minus operation” that is the inverse of the idempotent $$+$$.

This is why I don’t write “$$+$$” for or, but rather for $$operatorname{Xor}$$. The $$operatorname{Xor}$$ (eXclusive or) operator is better behaved.

If you set $$+$$ to be $$operatorname{Xor}$$, you get the equivalence you wanted :
$$varphi + psi = varphi + psi’ Longleftrightarrow psi = psi’$$

This is because every $$varphi$$ has an inverse for $$operatorname{Xor}$$, namely itself since $$varphi operatorname{Xor} varphi = 0$$.

Boolean algebra has no minus operation since the equation $$X + A = B$$ has no unique solution. Consider the case $$A=B=1.$$ Then both $$X=0$$ and $$X=1$$ are solutions.

## Math Genius: Interpreting truth tables for Knights and Knaves problems

Context: A person can either be a knight (always tells the truth) or a knave (always tells a lie).

On an island with three persons (A, B and C), A tells “If I am a knight, then at least one of us is a knave”.

Using the atoms P=A is a knight, Q=B is a knight, R=C is a knight, and the sentence \$Piff P rightarrow (neg P lor neg Q lor neg R)\$, I get the following truth table: How can I deduct that A is a knave based on this truth table? Is it because the equivalence is not a tautology? Thanks!

Actually you can deduct that A is a knight. Your sentence expresses what you now know after A speaks the sentence: namely, if A is a knight, then the sentence he spoke is true (these are the last four rows of your truth table), and thus at least one of B or C is a knave; if A is a knave, then the sentence he spoke is false (first four rows), which would mean that despite A being a knight none of the three are knaves. Of course, that doesn’t actually work, because in this case we already know that A is a knave.

The logical statement you wrote down is what you know to be true; hence, you are in a world where the final column of your truth table lists a T. That is, you know that A is a knight and at least one of B, C is a knave.

Suppose that he is correct.

Then, it follows that if none of them are knaves, then he is not a knight. So, if all of them are knights, then he is a knave.

The last line of your table indicates the case where all of them are knights. But, in such a case his (if … then …) assertion is false.

If we look at the 5th-7th rows of the table, those are the one rows where this equivalence holds true. If he is correct, then we’ll assume him a knight. Thus, by the rule of inference of reverse equivalence detachment {\$alpha\$, (\$beta\$ <-> \$alpha\$)} => \$beta\$, it follows that he is correct about his assertion. But, the above indicated that he would be knave. Therefore, he is a knave.

The truth table of A’s sentence is : Let’s consider case (1) that is, the case in which they are all knights. In that case , A’s sentence is false, and A is not a knight. So, they are not all knights, (because it is impossible, case (1) being inconsistent).

But cases (5) to (8) are also ruled out , for in thiese cases A is a knave and says someting true.

So, the only consistent ( hence, possible) cases are (2) to (4) in which A is a knight.

Other argument : A’s sentence is a conditional with a true consequent ( since they are not all knights, as we have seen). But such a conditional cannot be false ( by the truth-table of the ” if … then ” operator).

Tagged : /

## Math Genius: Can all proof systems be generically described?

Can every proof calculus (e.g. natural deduction, Hilbert-style axiomatic systems, sequent calculus) be expressed as a generic 4-tuple {A, Ω, Z, I} consisting of: set alpha of proposition symbols, omega set of operator symbols, zeta set of inference rules and iota set of axioms?

If yes, does it mean that, in principle, all syntax can be abstracted away and all proofs can be expressed as syllogisms of the form?:

`````` 1. ...
2. ...
...
N. ...
∴ ...
``````

How would e.g. Smullyan-style tableaux proofs (“truth trees”) fit into that picture?

Indeed, how would Gentzen-style natural deduction with its non-linear proof trees fit into the picture?

And what on earth is meant by talking of “syllogisms” here?

It is very unclear what insights could be gained by over-abstraction of this kind.

Tagged : / /

## Math Genius: Laws of logical equivalence

How do I solve this to show that the L.H.S = R.H.S

((p → q) ∨ (¬p → r)) → (q ∨ r) ≡ q ∨ r

I have to show this using the laws of logical equivalence.

I have made some attempt using implication law, associative law and commutative law, but I am not sure if these are the right laws and I am getting a bit confused. Help to solve this would be appreciated.

I have made some attempt using implication law, associative law and commutative law, but I am not sure if these are the right laws and I am getting a bit confused.

Yes, that is correct.  Begin by using implication equivalence on the antecedent’s implications, then associate and commute that disjunction.

begin{align}&((pto q)vee(neg pto r))to (qvee r)\[2ex]&((neg pvee q)vee(pvee r))to(qvee r)\[2ex]&((neg pvee p)vee(qvee r))to(qvee r)end{align}

Now you should see the next move.

## Math Genius: Are inference rules just tautologically (or syntactically) valid arguments?

“An argument is valid iff the following implication is a tautology: $$h_1∧h_2∧…∧h_n⇒C$$ where $$h_1∧h_2∧…∧h_n$$ are the hypothesis and $$C$$ the conclusion.”

A classic inference rule is modus ponens for example: $$A⇒B$$, $$A$$, therefore $$B$$. This is a valid argument, because $$(A∧(A⇒B))⇒B$$ is a tautology. This works for every inference rule.

So are inference rules just tautologically valid arguments (true in virtue of their form)? is this all they are?

One more doubt, if inference rule are valid arguments can i just “symbolize” modus ponens for example as: $$A⇒B,A⊧B$$ ? or there’s another symbol for that? One of my books uses the symbol “$$⇒$$” (and $$→$$ for implications) but i think it can be a little confusing..

Thank you!

The intent of syntactical inference rules is to reflect semantically valid inferences/arguments, yes.

However, there is no requirement that inference rules be valid. You can define inference rules any which way you want. My favorite invalid inference rule is:

$$frac{}{therefore P}qquad text{(hokus ponens)}$$

because this will allow me to complete any formal proof in 1 step 🙂

A second thing to notice is that inference rules typically reflect baby inferences, i.e. inferences that are obviously valid. We typically do not like to have very complicated (but valid) arguments as our inference rules; the whole conceptual idea of formal proofs is to break things down into those baby inferences: if we see that each of the individual inferences are valid, then we can be confident that the whole argument is valid as well. We can then treat that whole argument as a Lemma, maybe, but treating the whole argument as an inference rule defeats this purpose.

• Arguments appear at the language level; an argument is a string of formulas.

• Any talk aboud validity ( semantic or syntactic) belongs to the metalanguage level. You cannot say ” this formula or this inference is valid” inside the logical language.

• Inference rules belong to the metalanguage level: when I state an inference rule, I am not performing an inference, I am stating what one is allowed or even should to do while performing an inference : ” from $$(phi rightarrow psi)$$ and $$phi$$, infer $$psi$$“.

Analogy : when I state the rule ” Sentence –> Noun Phrase + Verb Phrase”, I am not using english language; I am talking about english language ( namely, about its syntax).

• Most inference rules correspond to a parallel metalogical statement according to which a given formula is a logical law/ truth ( i.e. a tautology).

Example : corresponding to the metalogical statement above is the metalogical statemment ” the formula $$[(phi rightarrow psi) land phirightarrow psi]$$ is a tautology”.

• But this is not always the case : the conditional proof rule has no corresponding tautology.