Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

51
votes
19answers
6k views

In classical logic, why is $(p\Rightarrow q)$ True if both $p$ and $q$ are False?

I am studying entailment in classical first-order logic. The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is: $$\begin{array}{|c|c|c|} ...
25
votes
4answers
674 views

Associativity of $\iff$

In this answer, user18921 wrote that the $\iff$ operation is associative, in the sense that $(A\iff B)\iff C$ $A\iff (B\iff C)$ are equivalent statements. One can brute-force a proof fairly ...
22
votes
10answers
15k views

In classical logic, why is $(p\Rightarrow q)$ True if $p$ is False and $q$ is True?

Provided we have this truth table where "$p\implies q$" means "if $p$ then $q$": $$\begin{array}{|c|c|c|} \hline p&q&p\implies q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ ...
18
votes
8answers
3k views

Assumed True until proven False. The Curious Case of the Vacuous Truth

Given two statements, $P$ and $Q$, and the logical connective, $\implies$, the truth table for $P \implies Q$ is: $$\begin{array}{ c | c || c | } P & Q & P\Rightarrow Q \\ \hline \text T ...
16
votes
5answers
577 views

If both $P$ and $Q$ are true , how can I tell that $P$ implies $Q$?

I am trying to understand the fundamentals of mathematical logic in order to be able to study discrete mathematics and computer science soon. I have a big problem understanding Implication. I ...
14
votes
2answers
2k views

Do De Morgan's laws hold in propositional intuitionistic logic?

In Wikipedia page on intuitionistic logic, it is stated that excluded middle and double negation elimination are not axioms. Does this mean that De Morgan's laws, stated $$ \lnot (p \land q) \iff ...
14
votes
3answers
981 views

In axiomatization of propositional logic, why can uniform substitution be applied only to axioms?

I'm reading an introductory book about mathematical logic for Computation (just for reference, the book is "Lógica para Computação", by Corrêa da Silva, Finger & Melo), and would like to ask a ...
13
votes
1answer
989 views

Minimum number of different clues in a Sudoku

I wonder if there are proper $9\times9$ Sudokus having $7$ or less different clues. I know that $17$ is the minimum number of clues. In most Sudokus there are $1$ to $4$ clues of every number. ...
11
votes
4answers
1k views

Why is a statement “vacuously true” if the hypothesis is false, or not satisfied?

Why isn't a conditional statement said to "not apply" instead of be "vacuously true" if the hypothesis is not satisfied? That would seem more appropriate.
11
votes
1answer
253 views

Representing predicate logic as arithmetic

Summary Since the below is quite long, I thought I'd add this summary. Given the following: A statement in proposition logic can be converted to an arithmetic expression over the integers modulo ...
10
votes
6answers
2k views

How to demystify the axioms of propositional logic?

How might I go about getting some intuition on the typical axiom schemes given for propositional logic? They seem rather mysterious at first glance. For example, these are taken from: ...
10
votes
5answers
2k views

What is a false premise?

I don't understand what a sound argument is. And what does it mean for a premise to be false? Why does case 3 (A is false, B is true) not apply in the real world? Here the author says that the first ...
10
votes
2answers
502 views

What is the converse of this statement and is it true?

If $a$ and $b$ are relatively prime, $a\mid c$ and $b\mid c$, then $(ab)\mid c$. I am lost. Would the converse be "If $(ab)\mid c$, then $a$ and $b$ are relatively prime and $a\mid c$ and $b\mid c$" ...
10
votes
2answers
140 views

Mystery Men Movie - Propositional Logic

In the movie Mystery Men, there is this scene: Captain Amazing (good guy): I knew you couldn't change. Casanova Frankenstein (bad guy): I knew you'd know that. Captain Amazing: Oh, I know. And ...
9
votes
9answers
2k views

I can't understand logical implication

I just started studying logic (high school) anyway...for the truth table of logical implication If sentence $A$ is true and $B$ is true then $A\implies B$ is true. does that mean if $A$ and $B$ are ...
9
votes
2answers
28k views

How to convert to conjunctive normal form?

If i have a formula: $((a \wedge b) \vee (q \wedge r )) \vee z$, am I right in thinking the CNF for this formula would be $(a\vee q \vee r \vee z) \wedge (b \vee q \vee r \vee z) $? Or is there some ...
8
votes
6answers
3k views

Help to understand material implication

This question comes from from my algebra paper: $(p \rightarrow q)$ is logically equivalent to ... (then four options are given). The module states that the correct option is $(\sim p \lor q)$. ...
8
votes
6answers
990 views

What is a constructive proof of $\lnot\lnot(P\vee\lnot P)$?

Glivenko's theorem says that $\lnot\lnot P$ is a theorem of intuitionistic logic whenever $P$ is a theorem of classical logic. Is it closely related to the so-called Gödel–Gentzen negative translation ...
8
votes
2answers
4k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
8
votes
9answers
1k views

Conditional Statements: “only if”

For some reason, be it some bad habit or something else, I can not understand why the statement "p only if q" would translate into p implies q. For instance, I have the statement "Samir will attend ...
8
votes
4answers
776 views

Is the following a valid mathematical statement?

For all $f:\mathbb N\to\{1,2,3,\ldots,100\}$, If $f$ is a one to one correspondence, Then $f^{-1}(2)=3$ It seems as though this should not be a valid statement, since the implication fails to ...
8
votes
3answers
229 views

How to deduce that something does not follow?

Assume I have formulas $H$, $P$ and $Q$. Assume further that I can show in classical logic that $P$ follows from $H$: $$H \vdash P$$ And that the negation of $Q$ follows from $H$: $$H \vdash \neg ...
8
votes
7answers
6k views

Associativity of logical connectives

According to the precedence of logical connectives, operator $\rightarrow$ gets higher precedence than $\leftrightarrow$ operator. But what about associativity of $\rightarrow$ operator? The implies ...
8
votes
4answers
337 views

How or why does intutionistic logic proof negations from within the theory, constructively?

I'm having a little of a cognitive dissonance why, in intuitionistic logic, it's possible to show stentences like $(\neg A \land \neg B) \implies \neg(A\lor B).$ In plain text: If 'A isn't true' as ...
8
votes
3answers
1k views

Why Peirce's law implies law of excluded middle?

Why if in a formal system the Peirce's law $((P\rightarrow Q)\rightarrow P) \rightarrow P$ is true, the law of excluded middle $P \lor \neg P$ is true too?
8
votes
2answers
80 views

How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?

For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - ...
8
votes
2answers
230 views

My professor says this is NOT a typo, but this does not appear to be logically valid.

$$\begin{array}{rlll} 1. & \sim H\lor \sim G & \text{Premise} & \\ 2. & H\& (G\lor H) & \text{Premise} & \text{DEDUCE $F\& H$} \end{array}$$ Using the rules ...
8
votes
3answers
2k views

Proof of the Compactness Theorem for Propositional Logic

I have a problem understanding the proof for the compactness theorem for propositional logic in my logic course. The compactness theorem states that there is a model for an infinite set $S$ of ...
7
votes
5answers
506 views

Equivalence of $a \rightarrow b$ and $\lnot a \vee b$

Is there a proof for the logical equivalence of $a \rightarrow b$ and $\lnot a \vee b$?
7
votes
5answers
1k views

Is $(p \to q) \to r$ logically equivalent to $p \to (q \to r)$?

Is $(p \to q) \to r$ logically equivalent to $p \to (q \to r)$? I try to simply each one, I got $\lnot ( \lnot p \lor q) \lor r$ and $\lnot p \lor ( \lnot q \lor r)$ respectively, then I am stuck. ...
7
votes
5answers
1k views

Logical NOT of an implication

I was looking through my notes but I was unable to find the answer to this, which I need to start am assignment question. What would the following be, in terms on moving the negation inside the ...
7
votes
5answers
244 views

The deep structure of logical formulas

A long-standing question to which I never found a concise answer is: Is there something like an unambiguous deep structure of a formula of propositional logic, opposed to its comparingly ...
7
votes
4answers
212 views

Showing $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ {without truth table}

Problem: Show $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ Source: As was noted in the original post, this problem is from Daniel J. Velleman's book ...
6
votes
5answers
243 views

Overlap of Propositional Logic and Elementary Set Question

I am a bit stuck on a basic sets problem: We know from resolutions that $(p \lor q) \land (\neg p \lor r) \to q \lor r$. Use this fact to show that $(P \cup Q) \cap (\overline{P} \cup R) \subseteq ...
6
votes
3answers
654 views

Modus Ponens vs implication?

What is the difference between Modus Ponens and an implication? If so, could you please give a simple example to help understanding?
6
votes
3answers
21k views

De-Morgan's theorem for 3 variables?

The most relative that I found on Google for de morgan's 3 variable was: (ABC)' = A' + B' + C'. I didn't find the answer for my question, therefore I'll ask here: ...
6
votes
3answers
119 views

Difference between Gentzen and Hilbert Calculi

What is the difference between Gentzen and Hilbert Calculi? From my understanding from the reading of Rautenberg's Concise Introduction to Mathematical Logic, Gentzen calculus is based on sequents ...
6
votes
8answers
976 views

General form of a proof that $ab=0 \implies a=0 \lor b=0$

When proving that $ab = 0 \implies a = 0 \,\mbox{ or }\,b = 0$ for members $a$ and $b$ of a field, I used an argument like Suppose $ab = 0$ and $a \ne 0$ ... then $b = 0$. Now suppose $ab = 0$ and ...
6
votes
3answers
377 views

How complicated is the set of tautologies?

Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$. How ...
6
votes
2answers
154 views

Sentential Logic

Below is a question comes from the book How to Prove It written by Daniel J. Velleman. Let $P$ stand for the statement, “I will buy the pants” and $S$ for the statement “I will buy the shirt.” ...
6
votes
1answer
945 views

Mendelson's Logic book “cheats” in the propositional calculus?

In Mendelson's book ("Introduction to mathematical logic") he defines truth values for sentences in the propositional calculus using truth tables. However, it seems to me he assumes implicitly that ...
6
votes
5answers
344 views

Is a proposition about something which doesn't exist true or false?

Let S = {x | x is not an element of x } The set S doesn't exist. Then, would a proposition such as "The cardinality of S is 1," be true or false? Equivalently, I could have made a proposition, "the ...
6
votes
2answers
695 views

Why is propositional logic not Turing complete?

According to 1 (probably not the most relevant source), propositional logic is not Turing complete. Aren't all computations in computers performed using logic gates, which can be represented as ...
6
votes
1answer
142 views

Intuitionistic proof of $\neg\neg(\neg\neg P \rightarrow P)$

How do you prove $\neg\neg(\neg\neg P \rightarrow P)$ in intuitionistic logic? I know this statement to be intuitionistically provable because of Glivenko's theorem. However, I wish to prove it ...
6
votes
2answers
167 views

Propositional Logic: Proof involving only the symbols $\{\rightarrow,F \}$

I feel like I literally tried everything. I'm exhausted, and could really use some help. I was instructed to prove some logic proposition using only the symbols $\{\rightarrow,F \}$. Let me first ...
6
votes
2answers
112 views

The logical law of closed systems of sentences

Consider the usual logical connectors $\wedge, \vee, \supset, \neg$ (i.e., "and", "or", material implication, negation) and the "stroke" $/$ defined as $p / q := (\neg p) \vee (\neg q)$. In his book ...
6
votes
2answers
392 views

**Competition** Shortest Proof of Lukasiewicz's 13 Letter Axiom for Implicational Calculus from Tarski-Bernays

Spurred on by Willemien's competition, I thought I'd post my own. In 1948 a paper by Jan Lukasiewicz got published that established a 13 letter formula as (one of?) the shortest single axioms, under ...
6
votes
1answer
399 views

distribution of categorical product (conjunction) over coproduct (disjunction)

In the classical and intuitionistic propositional calculi, it is straightforward, using natural deduction, to derive $((A \land C) \lor (B \land C))$ from $(A \lor B) \land C$: Assume $(A \lor B) ...
6
votes
2answers
126 views

Law of Clavius explained

Law of Clavius states $ \sim P \Rightarrow P \vdash P$ And the only explanation I sort of understand is ...
6
votes
1answer
252 views

How to formally prove the negation of a statement “A if and only if B”?

Motivated by this question, I'm trying to establish a logical proof to the fact that the following statement is false: $2x+1$ is prime if and only if $x$ is prime. There are several ways to ...