The Propositional Calculus

Banno

A forum on philosophy ought have threads on the basics of logic.

I am no logician, although I did do a few undergrad courses half a century ago and have read a bit since. So what I write might be wrong. This is at least partly about seeing what I can remember. There are real logicians hereabouts, and many more folk who think they understand logic but have no idea. Your task might be to learn how to recognise them. This thread might help

So here is a thread on propositional logic, to play with on rainy days. Starting with rules of syntax, it might grow to explain modus ponens, axiomatic systems and perhaps consistency and completeness. If that works we might start another thread on first-order logic.

https://openlogicproject.org

Srap Tasmaner

↪Banno

Why not just send everyone to Peter Smith's blog?

Banno

Propositional logic is about propositions.

Sometimes folk say that it is about statements, because a proposition is the intangible thing that "it is raining" has in common with "il pleut". For the most part the terms "proposition" and "statement" will be interchangeable.

What's pertinent is that propositional calculus treats the propositions as whole things, not getting in to the details of the things named or there attributes. That's the job of predicate calculus, with all the x's, a's, f's and funny quantifiers.

What we want to do is to examine the relations between these propositions, rather than their contents. And we don't want to deal with any particular propositions, like "snow is green" or "Fred is English". So here we will just write a letter for any proposition. And following convention we will start at "p", I suppose because "proposition" starts with a p. The proceeding alphabetically, we can write p, q, r, and so on, with the presumption that this sequence does not finish at z but goes on as far as you like, including to infinity and beyond.

Banno

↪Srap Tasmaner

'cause that doesn't test my memory, nor start a conversation here.

Srap Tasmaner

Let me put it this way.

A forum on philosophy ought have threads on the basics of logic. — Banno

I disagree. I've done my share of teaching some basic logic here, helping folks with homework, answering questions. We should do that. But we should point people learning from scratch, especially on their own, to better resources.

In fact, for many sorts of questions, stackexchange is a better resource than us.

I understand why you might want to brush up, but why should we watch?

Maybe I just don't understand what sort of conversation you expect to have by presenting textbook material. Are we going to do philosophy of logic? If so, why the textbook review?

Banno

Well-formed formulae

Next we need some rules about what one can write.

There's a few other symbols. These are ~, &, v, ⊃ and ≡. They have names in English, but for now we might leave that aside and treat them just as arbitrary signs. There are rules for how we can use these symbols. We can't just write anything, like

&pv~~⊃

Some string of symbols are well-formed, others are not.

As already mentioned, we are allowed to write any lower-case letter, like

p

or

q

and so on.

And lets invent symbols for any well-formed formulae( wff): ϕ, ψ and so on

Now we can write the rule:

If ϕ is a wff, then ~ϕ is a wff

So since "p", we can now also write "~p". And since we can write "~p", we can write "~~p", and so "~~~p" and so on. The process is iterative.
We can do the same for the other symbols. We get the formation rules:

If ϕ and ψ are wff, then

~ϕ is a wff
ϕvψ is a wff
ϕ&ψ is a wff
ϕ⊃ψ is a wff
ϕ≡ψ is a wff

Banno

I understand why you might want to brush up, but why should we watch? — Srap Tasmaner

You don't have to watch. Go do something else.

Srap Tasmaner

↪Banno

I asked why we should watch, and you answered that I don't have to.

That is not logical, Captain.

But I'll take your "suggestion" to go away. Best of luck with your new blog.

Banno

Truth tables

Our p's and q's are standing in for propositions or sentences. Propositions and sentences are the sort of thing that can be either true or false, and we can assign a T or an F to them, to show this:

+---+
| p |
+---+
| T |
+---+
| F |
+---+

and assign values to the other symbols,

+---+----+
| p | ~p |
+---+----+
| T | F  |
+---+----+
| F | T  |
+---+----+

and generalise this for any WFF

+---+----+
| ϕ | ~ϕ |
+---+----+
| T | F  |
+---+----+
| F | T  |
+---+----+

So colloquially, if some proposition is true, then it's negation is false and if some proposition is false, its negation is true.

Banno

Best of luck with your new blog. — Srap Tasmaner

Thanks. I'm kinda hoping that other folk might butt in and add stuff.

I'm. using https://www.tablesgenerator.com/text_tables# to make generating tables a bit easier.

Banno

And we can continue for a few more of the symbols:

+---+---+-------+
| ϕ | ψ | ϕ & ψ |
+---+---+-------+
| T | T |   T   |
+---+---+-------+
| T | F |   F   |
+---+---+-------+
| F | T |   F   |
+---+---+-------+
| F | F |   F   |
+---+---+-------+

Some notations just us a dot "." for "&", or "∧".

Here we see the similarity to the English connective, "and".

and

+---+---+-------+
| ϕ | ψ | ϕ v ψ |
+---+---+-------+
| T | T |   T   |
+---+---+-------+
| T | F |   T   |
+---+---+-------+
| F | T |   T   |
+---+---+-------+
| F | F |   F   |
+---+---+-------+

This differs somewhat from one common colloquial use. In colloquial English if you are offered the chocolate cake or the cheesecake you would be expected to chose one or the other, but not both. Here, you can have both. It's called an inclusive OR, the alternative being an exclusive OR.

+---+---+-------+
| ϕ | ψ | ϕ ⊃ ψ |
+---+---+-------+
| T | T |   T   |
+---+---+-------+
| T | F |   F   |
+---+---+-------+
| F | T |   T   |
+---+---+-------+
| F | F |   T   |
+---+---+-------+

The "⊃" is called a hook, and is sometimes represented by a →. Colloquially it is "if ϕ then ψ".

Agent Smith

My two cents:

The Laws of Thought

1. Identity A = A
2. The law of the excluded middle p v ~p
3. The law of noncontradiction ~(p & ~p)

---

The simplest argument form modus ponens (abbrev. MP)
1. p $\to$ q
2. p
Ergo
3. q

---

Formal fallacies associated with modus ponens

Denying the antecedent/Inverse fallacy
1. p $\to$ q
2. ~p
Ergo
3. ~q

Affirming the consequent/Converse fallacy
1. p $\to$ q
3. q
Ergo
4. p

Banno

1. Identity A = A — Agent Smith

Cheers.

The law of identify holds between individuals, and as mentioned earlier propositional calculus deals in whole propositions. SO strictly the law of identity is a part of predicate clacualus rather then propositional calculus.

Here's the truth table for excluded middle:

+---+----+--------+
| p | ~p | p v ~p |
+---+----+--------+
| T | F  |    T   |
+---+----+--------+
| F | T  |    T   |
+---+----+--------+

and for noncontradiction

+---+----+----------+-----------+
| p | ~p | (p & ~p) | ~(p & ~p) |
+---+----+----------+-----------+
| T | F  |     F    |     T     |
+---+----+----------+-----------+
| F | T  |     F    |     T     |
+---+----+----------+-----------+

Notice that it is the negation of (p & ~p), a contradiction?

The contradiction has "F in each row in the truth table. The tautology has T.

So the first way we have of proving a theorem is looking at its truth table.

Agent Smith

The law of identify holds between individuals, and as mentioned earlier propositional calculus deals in whole propositions. SO strictly the law of identity is a part of predicate clacualus rather then propositional calculus — Banno

Noted! I don't want to go into the formal aspects of the law of identity and I guess you share that sentiment. Let's leave it at the level of intuitive understanding, that a thing is identical to itself, for the moment.

Notice that it is the negation of (p & ~p), a contradiction?

The contradiction has "F in each row in the truth table. The tautology has T.

So the first way we have of proving a theorem is looking at its truth table. — Banno

The point to truth tables is that given a set of rules on how logical connectives (&, v, ~, $\to$ ) function (quite like mathematical operations),

a) What will be the final truth value of compound statements like A & C or B v T or E $\to$ I or ~W or more complex compound statements.

b) Evaluate for validity of an argument: Is there a possible world in which, for a given argument form, all the premises are true and the conclusion false? If there is, the argument is invalid and if there's none, the argument is valid.

c) Check for consistency. Is there a possible world in which all the propositions are true? If yes, the set of propositions in question are consistent; if no, inconsistent (we can derive a contradiction via conjunction).

---

To pick up where I left off (for those interested).

Argument form: Modus tollens (abbrev. MT)

1. p $\to$ q
2. ~q
Ergo
3. ~p

Banno

There's two ways to proceed from here. One is to set up an axiomatic system and proceed from there. The other is to instead set up some rules of deduction and proceed from those - a system of natural deduction. I'd like to do both.

But natural deduction is more common and more direct, so we might start there.

Agent Smith

But natural deduction is more common and more direct, so we might start there. — Banno

Solid copy!

Argument form: Disjunctive syllogism (abbrev. DS)

1. p v q
2. ~p
Ergo
3. q

Agent Smith

Argument form: Hypothetical syllogism (abbrev. HS)

1. p $\to$ q
2. q $\to$ r
Ergo
3 p $\to$ r

Banno

The point to truth tables is that given a set of rules on how logical connectives function (quite like mathematical operations), what will be — Agent Smith

Sure, but they have an additional role in showing which wff are tautologies, which are contradictions and which are neither.

If the column for some wff is all T's, it's a tautology; it's never false. If they are all F's it's a contradiction. If it's a mix, then it is contingent - it depends on the value of each proposition.

Evaluate for validity of an argument: Is there a possible world in which, for a given argument form, all the premises are true and the conclusion false? If there is, the argument is invalid and if there's none, the argument is valid. — Agent Smith

Te use of "possible world" is problematic here. Possible worlds are used in modal logic, which again comes after (builds on) predicate logic, which is turn builds on propositional logic. Small steps.

Consider the table for ( p & q):

+---+---+-------+
| p | q | p & q |
+---+---+-------+
| T | T |   T   |
+---+---+-------+
| T | F |   F   |
+---+---+-------+
| F | T |   F   |
+---+---+-------+
| F | F |   F   |
+---+---+-------+

Whether ( p & q) is true or not depends on the values of p and of q. As the table shows, in the first row, if both o and q are true then (p & q) will be true. But, as the remaining rows show, if either or both are false, the conjunction ( p & q) will also be false.

But consider (p & ~p)

+---+----+----------+
| p | ~p | (p & ~p) |
+---+----+----------+
| T | F  |     F    |
+---+----+----------+
| F | T  |     F    |
+---+----+----------+

In this case, whether P is true or false makes no difference, the conjunction will aways be false. Now look at (p v ~p)

+---+----+----------+
| p | ~p | (p v ~p) |
+---+----+----------+
| T | F  |     T    |
+---+----+----------+
| F | T  |     T    |
+---+----+----------+

in this case, regardless of whether p is true or false, (p v ~p) is true.

Nothing to do with possible worlds.

Agent Smith

Nothing to do with possible worlds. — Banno

I thought each truth value assignment specified a possible world. So given a proposition p, p is T is one world and p is F is another, it being impossible for p to be T and F in one world (LNC).

T = True
F = False
LNC = The law of noncontradiction

Banno

↪Agent Smith

Not quite. p can be any proposition, from "the cow needs milking" to "the square on the hypotenuse is equal to the sum of the squares on the other two sides" and all things else. So

the cow needs milking or the cow does not need milking

will always be true; (p v ~p).

But

the cow needs milking and the cow does not need milking

will never be true; (p & ~p).

And

"the cow needs milking and the cat is having kittens"

might be either; (p & q).

We don't ned talk of possible world yet. Only of different propositions and their relations.

Agent Smith

↪Banno

ok

Banno

↪Agent Smith

...you don't sound convinced...

So you have been doing a rough form of natural deduction in your posts.

In natural deduction, any well formed formula can be take and an assumption. What we do then is to use a few rules of deduction to work out the consequences of those assumptions.

To this we add modus ponens, as you described it:

1. p → q
2. p
Ergo
3. q

We might set it out as

1. p (A)
2. p⊃q (A)
---------
3. q. (1,2,MP)

It's the same, just adding in brackets the justification for the deduction. (A) is an assumption, (1,2,MP) says we deduce line 3 from lines 1 and 2 by modus ponens.

Some systems write MPP for modus ponendo ponens. You might be interested in the Latin.

The line just equates to "ergo".

Banno

A more complex example

1. p⊃q (A)
2. q⊃r (A)
3. p (A)

the conclusion?

Reveal

4. q (1,3,MP)
5. r (2,4,MP)

Or

1. p⊃(q⊃r) (A)
2. p⊃q (A)
3. p (A)

Reveal

4. q⊃r (1,3,MP)

Reveal

5. q (2,3,MP)

Reveal

6. r (4,5, MP)

Banno

A truth table proof of MP:

+----+---+----+---+----+---+---+
| (p | & | (p | ⊃ | q) | ⊃ | q |
+----+---+----+---+----+---+---+
| T  | T |  T | T | T  | T | T |
+----+---+----+---+----+---+---+
| T  | F |  T | F | F  | T | F |
+----+---+----+---+----+---+---+
| F  | F |  F | T | T  | T | T |
+----+---+----+---+----+---+---+
| F  | F |  F | T | F  | T | F |
+----+---+----+---+----+---+---+

All T's down the sixth column, which is the conclusion, hence MP is a tautology.

Ugly, but effective.

Agent Smith

...you don't sound convinced... — Banno

:blush:

I don't wanna derail a good thread.

Gracias for the explanation. :up: I just looked up natural deduction on Wikipedia & Stanford Encyclopedia of Philosophy. It goes into the details of the system, more than I can take on at the moment. To beginners like myself, natural deduction is a system developed to imitate how people actually reason without compromising on the rigor of more formal systems; hence the natural in the name.

Banno

I don't wanna derail a good thread. — Agent Smith

I need feedback.

↪Agent Smith

Yet natural deduction is as powerful and valid as an axiomatic system.

Banno

Two more rules for derivation are worth further comment, despite being mentioned by @Agent Smith.

Modus Tollens (MT) allows the following derivation:

1. p⊃q (A)
2. ~q. (A)
____
3. ~p (1,2 MT)

And double negation

1. ~~p
____
2. p (1, DN)

If we adopt the convention of ⊢ as "Therefore", and Greek letters ψ and ϕ (phi and psi) for any wff, we can list the derivations rules as follows:

A: Any wff may be assumed
MP: ϕ⊃ψ, ϕ, ⊢ψ
MT: ϕ⊃ψ, ~ψ, ⊢~ϕ
DN: ~~ϕ ⊢ϕ

Agent Smith

I need feedback. — Banno

:snicker: Well, to me, modal logic is part and parcel of propositional logic (thank goodness the OP is delimited to that; my predicate logic is rusty). Consider the definition of validity: An argument is valid if it is impossible for the premises to be true and the conclusion false. Mind you, my knowledge is limited to natural deduction as found in introductory texts on logic.

Yet natural deduction is as powerful and valid as an axiomatic system. — Banno

I'm afraid I won't be able to further the discussion on that point.

My responses are limited. You'll have to ask the right questions. — Dr. Lanning (I Robot)

Banno

↪Agent Smith

You are right that an argument is valid if it is impossible for the premises to be true and the conclusion false. The problem I anticipate is calling this modal logic.

Propositional logic deals in whole propositions and the connections between them. The next level is predicate logic, which takes the p's and q's of propositional logic and opens them up to expose the individuals and predicates that constitute them; so p becomes f(a). Modal logic goes a step further by adding prefixes to the propositions; usually necessarily p and possibly p: ☐p and ♢p; but in other variations terms for obligation, for tense (in a temporal sense), and for belief.

SO better to steer clear of talking of propositional calculus as modal.

Agent Smith

↪Banno

Ok. I don't have the skillset to engage in a worthwhile discussion on this topic. Will heed your advice (for now).

---

Can you take a look at a statement that appears on Wikipedia regarding natural deduction?

A theory [natural deduction] is said to be consistent if falsehood is not provable (from no assumptions)¹ and is complete if every theorem or its negation is provable using the inference rules of the logic². — Wikipedia

What do 1 and 2 mean exactly? My guesstimates below:

1. Falsehood = Contradiction

2. I have no clue. I thought completeness meant every true statement is provable.

Banno

↪Agent Smith

The calculus constitutes a formal language. Yep, the language will be consistent if it is not possible to derive any contradictions. It will be complete if we can derive every tautology.

The Propositional Calculus

Welcome to The Philosophy Forum!

Categories

More Discussions