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. — Banno

Ok :grin: You see, that's an explanation that needs an explanation in my pathetic universe. Don't worry, I'll work on the gaps in my knowledge, just not now; I have a lot on my plate.

The next derivation rule at first looks a tad odd. It's called Conditional Proof (CP)

Given any sequence

1. ϕ (A)
.
.
.
5. ψ (with whatever justification)
6. ϕ⊃ψ

CP allows us to take any assumption and put it before any deduction from that assumption. It serves to reduce the number of assumptions by one.

An example: show p⊃q ⊢ ~q⊃~p

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

Note how the assumption ~q is incorporated into the conclusion ~q⊃~p.

Argument form: Constructive dilemma (abbrev. CD)

1. p v q
2. p $\to$ r
3. q $\to$ s
Ergo
4. r v s

Nice. The Wikipedia page has a proof.

:up:

& introduction.
Given any two propositions, we can join then with &. (&I)

& elimination

Similarly, given any conjunction, we can drop one of the conjuncts. (&E)

Or Introduction

(vI) Given any proposition, we can stick it in a disjunction:


Or Elimination

(vE). More complex. If ϕvψ and both ϕ⊃ρ and ψ⊃ρ, then ρ

Argument form: Tautology (abbrev. Taut)

1. p & p
Ergo
2. p

---

1. p v p
Ergo
2. p

1. p & p
Ergo
2. p — Agent Smith

Nice. Lets' take a look at this. We can rewrite this as:

1. p&p. (A)
______
2. p (&I)

or on a single line as

p&p ⊢ p

Where again ⊢ is "therefore", we read "p and p therefore p"

Recall that conditional proof removes an assumption. Suppose we took a step further, and using Conditional Proof CP to remove the assumption:

1. p&p. (A)
2. p (&I)
_____
3. (p&p)⊃p (1,2,CP)

When we write this on a single line we no longer need the assumption (1); so

⊢(p&p)⊃p

The wff is true regardless of the assumptions made. A wff of this sort is called a theorem. A theorem is a wff that is proven with zero assumptions.

Consider:

:up:

For reference:

LANGUAGE

symbols:

sentence letters P Q R ...
connectives ~ v & -> <->
left and right parentheses ( )

formulas:

a sentence letter alone is a formula
if X and Y are formulas, then so are ~(X) (XvY) (X&Y) (X->Y) (X<->Y) [we omit parentheses if no confusion results*]
nothing else is a formula

* And if we used Polish notation, then we wouldn't need parentheses at all.

For reference:

BOOLEAN FUNCTIONS

A Boolean function is function* whose domain is, for some natural number k, the set of k-tuples over {0 1} and whose range is a subset of {0 1}.

* With the exception of '1' mentioned below as a 0-place function even though it is not an actual function.

There are two 0-place Boolean functions:

1
the value 'truth, sometimes represented by the constant 't'

0
the value 'falsehood', sometimes represented by the constant 'f'

There are four 1-place Boolean functions:

{<1 1>
<0 1>}
the constant function that maps any value to 'truth'

{<1 0>
<0 0>}
the constant function that maps any value to 'falsehood'

{<1 1>
<0 0>}
the identity function

{<1 0>
<0 1>}
negation

There are sixteen 2-place Boolean functions:

{<<1 1> 1>
<<1 0> 1>
<<0 1> 1>
<<0 0> 1>}

reduces to t

{<<1 1> 1>
<<1 0> 1>
<<0 1> 1>
<<0 0> 0>}

disjunction

{<<1 1> 1>
<<1 0> 1>
<<0 1> 0>
<<0 0> 1>}

converse of material implication

{<<1 1> 1>
<<1 0> 1>
<<0 1> 0>
<<0 0> 0>}

identity on the first coordinate

{<<1 1> 1>
<<1 0> 0>
<<0 1> 1>
<<0 0> 1>}

material implication

{<<1 1> 1>
<<1 0> 0>
<<0 1> 1>
<<0 0> 0>}

identity on the second coordinate

{<<1 1> 1>
<<1 0> 0>
<<0 1> 0>
<<0 0> 1>}

material equivalence

{<<1 1> 1>
<<1 0> 0>
<<0 1> 0>
<<0 0> 0>}

conjunction

{<<1 1> 0>
<<1 0> 1>
<<0 1> 1>
<<0 0> 1>}

negation of conjunction

{<<1 1> 0>
<<1 0> 1>
<<0 1> 1>
<<0 0> 0>}

negation of material equivalence

{<<1 1> 0>
<<1 0> 1>
<<0 1> 0>
<<0 0> 1>}

negation of the second coordinate

{<<1 1> 0>
<<1 0> 1>
<<0 1> 0>
<<0 0> 0>}

negation of material implication

{<<1 1> 0>
<<1 0> 0>
<<0 1> 1>
<<0 0> 1>}

negation of the first coordinate

{<<1 1> 0>
<<1 0> 0>
<<0 1> 1>
<<0 0> 0>}

negation of the converse of material implication

{<<1 1> 0>
<<1 0> 0>
<<0 1> 0>
<<0 0> 1>}

negation of disjunction

{<<1 1> 0>
<<1 0> 0>
<<0 1> 0>
<<0 0> 0>}

reduces to f


For k>2, a k-place Boolean function can be expressed as a combination of 2-place Boolean functions.

The connectives are interpreted as Boolean functions:

~ is interpreted as negation. You can see how the truth table for ~ is another way of representing this Boolean function.

v is interpreted as disjunction. You can see how the truth table for v is another way of representing this Boolean function.

& is interpreted as conjunction. You can see how the truth table for & is another way of representing this Boolean function.

-> is interpreted as (material) implication. You can see how the truth table for -> is another way of representing this Boolean function.

<-> is interpreted as (material) equivalence. You can see how the truth table for <-> is another way of representing this Boolean function.

There we mentioned only one 1-place connective and only four 2-place connectives. That's okay, because this is an adequate set to represent any other Boolean function by a combination of these connectives.


There are combinations of Boolean functions that are adequate too:

negation of conjunction ("not both")

negation of disjunction ("neither nor")

negation with disjunction

negation with converse of implication

negation with implication

negation with equivalence

negation with conjunction

negation with negation of equivalence

negation with negation of implication

negation with negation of converse of implication


In other words, these are adequate:

negation of disjunction

negation of conjunction

negation with any one of these: disjunction, conjunction, implication, negation of implication, equivalence, negation of equivalence, converse of implication, negation of converse of implication

For reference:

A NATURAL DEDUCTION SYSTEM:

Comment: Unlike quantifier logic with predicate symbols of arity greater than 1, sentential logic doesn't really need a calculus, because checking for sentential validity is mechanical (for example, using truth tables). But we like to give a calculus anyway:

Notation:

P, Q and R are any formulas

G, H and J are any sets of formulas

u for union

|- for implies


RULES:

Assumption

Enter P on a line and charge that line to itself.

{P} |- P
______

Deduction

If Q is inferred from P along with possibly other lines, then infer P->Q and charge it with all lines charged to Q except the line for P.

If Gu{P} |- Q, then G |- P->Q
______

Modus Ponens

From P and P->Q, infer Q and charge it with all lines charged to P and to P->Q.

If G |- P and H |- P->Q, then GuH |- Q
______

Intuitionistic Contradiction

If a contradiction is inferred from P, along with possibly other lines, then infer ~P and charge it with all lines charged to the contradiction except the line for P.

If Gu{P} |- Q and Hu{P} |- ~Q, then GuH |- ~P
______

Classical Contradiction

If a contradiction is inferred from ~P, along with possibly other lines, then infer P and charge it with all lines charged to the contradiction except the line for ~P.

If Gu{~P} |- Q and Hu{~P} |- ~Q, then GuH |- P
______

Conjunction Introduction

From P and Q, infer P&Q and charge it with all lines charged to P and to Q.

If G |- P and H |- Q, the GuH |- P&Q
______

Conjunction Elimination

From P&Q, infer P and charge it with all lines charged to P&Q.
From P&Q, infer Q and charge it with all lines charged to P&Q.

If G |- P&Q, then G |- P
If G |- P&Q, then G |- Q
______

Disjunction Introduction

From P, infer PvQ and charge it with all lines charged to P.
From Q, infer PvQ and charge it will all lines charged to Q.

If G |- P, then G |- PvQ
If G |- Q, then G |- PvQ
______

Disjunction Elimination

From PvQ, P->R and Q->R, infer R and charge it with all lines charged to PvQ and to P->R and to Q->R.

If G |- PvQ and H |- P->R and J |- Q->R, then GuHuJ |- R


DEFINITION:

P <-> Q stands for (P->Q)&(Q->P)

I vaguely recall reading and it seems possible that any statement/proposition in logic can be rephrased using only two connectives viz. OR (v) and NOT (~).

For example p $\to$ q = ~p v q and (p & q) = ~(~p v ~q).

It reminds me of how subtraction is rendered as addition of the opposite like so: a - b = a + (-b) [negative numbers] The same thing can be done with division thus: $a \div b = a \times \frac{1}{b}$ [fractions].

Any sentential formula has an equivalent using a combination of 'not' and 'or'. That is only one of the eight cases I mentioned where 'not' with another connective is adequate. Moreover, 'not both' (Sheffer stroke) is adequate by itself, and 'neither nor' (Nicod's dagger aka 'Pierce arrow') is adequate by itself'.

Sorry, this was goofy:
It is sometimes desirable to effect such a transformation into a form with only ORs and NOTs (disjunctive normal form) or only ANDs and NOTs (conjunctive normal form).

CNF and DNF are interesting, but not as described. It's a question of whether you have only ANDs outside and ORs inside parentheses or the other way around.

A & (~B v C) & (D v ~E) is CNF
(A & B) v (~C & D) v (~E & ~F) is DNF.

(Your question called them to mind, as getting something into a canonical form, but then I somehow didn't notice I was writing gibberish! Ah well.)

You can also get by with a single connective, if you're so inclined, the Sheffer stroke, " | ", read "not both," or NAND.

conjunction and disjunction are analogous with:

multiplication and addition in Boolean algebra

intersection and union in set theory

universal quantifier and existential quantifier in predicate logic

Each pair is a pair of duals.

Thanks.

* And if we used Polish notation, then we wouldn't need parentheses at all. — TonesInDeepFreeze

True, but no one would understand us.

Anyone remember programable calculators that used reversible polish notation? I recall using one that was the size of a typewriter... er, desktop PC.

existential quantifier and universal quantifier in predicate logic — TonesInDeepFreeze

Ah, interesting. From the definition of each: ∃(x)Fx≡ Fm v Fn v Fo... and (x)Fx≡Fm&Fn&Fo...?

My notes...
{<1 1>
<0 1>}
the constant function that maps any value to 'truth' — TonesInDeepFreeze

To read this, an input on the left gives the output on the right, so 1 gives 1 and 0 gives 1, hence always true...

{<1 0>
<0 0>}
the constant function that maps any value to 'falsehood' — TonesInDeepFreeze

...always false...

{<1 1>
<0 0>}
the identity function — TonesInDeepFreeze

...always the same...

{<1 0>
<0 1>}
negation — TonesInDeepFreeze

...always negated. And so on.

Muchas gracias. I'll read the linked article when I get the time.

OR (v) and NOT (~). — Agent Smith

Free will won't? Choices offered, one/more denied. :chin:

(Was an attempt to put all 16 truth functions of two variables into a table. Too ugly.)

∃(x)Fx≡ Fm v Fn v Fo... and (x)Fx≡Fm&Fn&Fo...? — Banno

If the domain is finite, then an existential statement is equivalent to a finite disjunction, and a universal statement is equivalent to a finite conjunction. But, in ordinary logic, there are no infinite disjunctions nor infinite conjunctions, but, for infinite domains, we can think of the quantifiers as "in a sense" representing "infinite disjunctions" and "infinite conjunctions".

Notice that:

ExS <-> ~Ax~S compares with (P v Q) <-> ~(~P & ~Q)

AxS <-> ~Ex~S compares with (P & Q) <-> ~(~P v ~Q)

Too ugly. — Banno

Lookism? In the ideaverse? No wonder some of these memes - the aesthetically challenged ones in all likelihood - override our self-preservation instincts and make us fatally courageous.

I'm slowly heading this thread towards a proof of consistency, then perhaps completeness.

To that end, and because it seems at first odd, i'd like to point out that an inconsistent language - or theory, if you prefer - is one in which any and every theorem can be deduced; on in which everything is true.

Take ϕ to be any theorem at all.

Then since we can write:

(p & ~p) ⊃ ϕ

if a contradiction is true in our system, then anything is derivable.

So conversely, if just anything is derivable, the system is inconsistent.

And so, if there are things that cannot be derived, then the system is consistent...

That's an outline of one strategy for a proof of consistency.

Great! You brought up contradiction. When I first encountered contradictions in real life, back when I was in my teens & later on, it was, now I realize, incomprehensible or incomputable (that was the pre-logic phase of my life). I couldn't make sense of it at all. I reasoned to myself there's something fundamentally wrong with statements like p & ~p. It's snowing AND it's not snowing is "wrong" for the reason that the the second conjunct denies/negates the first - they cancel each other out and its as if someone who utters/writes a contradiction says nothing at all (+y + -y = 0].

Those who know don't speak, those who speak don't know. — Laozi

"What a genuine word of God would look like?"
— Art48

Silence. — Banno

अति सुंदर

(Ati sundar: Glorious/most beautiful).

Accounts of God having answered prayers is total hogwash! That however doesn't mean we stop praying. — Agent Smith

Then I took an introductory course in logic and came to realize formalization (logic to logicians) meant that contradictions, their unacceptability to be precise, need to be put on firmer ground than just than intuition I outlined in the previous paragraph. This, I came to know, takes shape in the famous ex falso quodlibet (anything follows from a contradiction). How this happens is as follows:

1. p & ~p
2. p [1 Simp]
3. p v q [2 Add]
4. ~p [1 Simp]
5. q [3, 4 DS]

q here stands for any and all statements & even their negations [you mentioned inconsistency and this is it].

According to logicians, contradictions, and I quote, "trivialize the notion of truth". What this means isn't clarified in the books I read. What does it mean Banno? If p is true and ~p is also true, I would say that negation (~) is being trivialized (it doesn't matter whether its present/absent). Please help! :smile:

. I reasoned to myself there's something fundamentally wrong with statements like p & ~p. It's snowing AND it's not snowing is "wrong" for the reason that the the second conjunct denies/negates the first - they cancel each other out and its as if someone who utters/writes a contradiction says nothing at all (+y + -y = 0]. — Agent Smith

If contradictions are just like equations which equal zero, then the conclusion from snowing and not snowing would be "nothing". So it couldn't be the case that "anything" follows from contradiction, because "nothing" is not the same as "anything". But "nothing" is really wrong, because snowing and not snowing are statements concerning "snowing", and negating that subject does not produce nothing in the most general sense, it leaves alone everything else except "snowing", where the contradiction creates a problem.

OK!

According to logicians, contradictions, and I quote, "trivialize the notion of truth". — Agent Smith

Following on from the previous posts, if any proposition follows from a contradiction, then if the contradiction is true, any proposition is true; that is, there is no longer a difference between a true and false propositions, and so every proposition is true: truth is trivial.

Following on from the previous posts, if any proposition follows from a contradiction, then if the contradiction is true, any proposition is true; that is, there is no longer a difference between a true and false propositions, and so every proposition is true: truth is trivial. — Banno

I still don't get it! I need another example of triviality to help me grasp the notion of trivializing. I read the Google definition and it says trivializing is to reduce the importance or significance of something.

I've encountered the notion of the trivial in mathematics. Take Fermat's last theorem: $a^n = b^n + c^n$ for n $\neq$ 2 (where n = 2, we have Pythagoras' theorem). The trivial solution is n = 0. What does "trivial" mean in this case? Does it mean obvious and/or uninteresting? I think it means the latter but can't say for sure.