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)

57
votes
19answers
7k 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|} \...
26
votes
11answers
17k 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\\ F&...
25
votes
4answers
727 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 ...
21
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 &...
17
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 \...
17
votes
5answers
589 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
3answers
1k 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
996 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. ...
12
votes
7answers
3k views

Show that (p ∧ q) → (p ∨ q) is a tautology?

I am having a little trouble understanding proofs without truth tables particularly when it comes to → Here is a problem I am confused with: Show that (p ∧ q) → (p ∨ q) is a tautology The first ...
12
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.
12
votes
2answers
153 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 ...
11
votes
6answers
3k 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: http://en....
11
votes
1answer
294 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 2,...
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
515 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
3answers
2k 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?
10
votes
4answers
355 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 ...
10
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 ...
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
6answers
1k 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 ...
9
votes
2answers
34k 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 ...
9
votes
2answers
5k 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 $q$...
9
votes
7answers
7k 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
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
3answers
25k 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: ...
8
votes
9answers
2k 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
827 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
244 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
2answers
87 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
234 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 of ...
7
votes
5answers
535 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
3answers
178 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 ...
7
votes
5answers
251 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
237 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
245 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
928 views

Proof of (P → Q) from ¬P?

I'm trying to figure out how to prove P → Q from just ¬P. I can deduce it using informal logic. Since the only way a conditional is False is in the case of T → F, if P is False, P → Q must always be ...
6
votes
3answers
763 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
700 views

Give a proof that “p & ~p” implies “q”?

Context: This is not a textbook or homework problem. I was hoping you younger folks could help my tired old brain. "Everybody knows" a contradiction implies anything. What I'm looking for is a ...
6
votes
3answers
9k views

What is Validity and Satisfiability in a propositional statement?

I tend to see these words a lot in Discrete Mathematics. I assumed these were just simple words until I bumped into a question. Is the following proposition Satisfiable? Is it Valid? $(P \...
6
votes
8answers
1k 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
402 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
168 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
994 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
399 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
3answers
12k views

Problem in understanding p implies q

I am trying to understand what “$p$ implies $q$” means. I read that $p$ is a sufficient condition for $q$, and $q$ is a necessary condition for $p$. Further from Wikipedia, A ...
6
votes
2answers
795 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
176 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
185 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 ...