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)

1
vote
1answer
56 views

Classical and intuitionistic propositional logic in the propositions-as-sets interpretation

I'm looking for a way to describe classical and intuitionistic propositional logic such that the transition between the two seems natural and intuitive. I came up with the following but I'm unsure if ...
2
votes
1answer
56 views

Best way to introduce Curry-Howard isomorphism

I want to give a small talk about the Curry-Howard isomorphism to people who are not familiar with intuitionistic logic. Personally, I think about intuitionistic logic just in the ...
0
votes
1answer
36 views
2
votes
1answer
27 views

Different propositional logics in Sodoku

I have started reading Rosen's Discrete Mathematics and I have reached the topic of propositional satisfiability and it's application in solving Sudoku. Solving such puzzles consists of solving the ...
3
votes
4answers
68 views

Logic : One person speaks Truth only but the other one only Lies.

In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without ...
1
vote
0answers
54 views

Is propositional logic enough to study real analysis?

Is it necessary to study relational logic before starting real anylisis(from Bartle and Scherbert) or propositional logic enough? Also for topics like topology and differential geometry is ...
0
votes
2answers
50 views

How can I solve this logic question using propositional logic (Natural deduction)?

$$\big((P\rightarrow Q)\rightarrow P\big) \rightarrow P$$ I need to solve this using simple natural deduction rules these can be hypothesis, $\rightarrow$ intro, $\rightarrow$ elim, conj and ...
1
vote
0answers
19 views

Converting equivalence to CNF

I have the following scenario which I need to represent in CNF: we have $n$ bins, and $A_{ij}$ holds iff balls $i$ and $j$ are in a consecutive pair of bins such that the first bin of the pair is ...
3
votes
3answers
470 views

can we continue a proof by contradiction even if we get to a contradiction?

consider the example below : our set of premises are $\{ a , b , a \to c , b \to a \}$ and we want to prove $c$ is true . someone has used proof by contradiction to prove this . the proof : ...
1
vote
1answer
20 views

converting predicate logic to clause form

Lets say we have a statement in predicate logic which we have to convert to clause form to apply unification: $ \forall x, P1(x) \vee P2(x) \Rightarrow P3(x) $ or, $ \exists x,\neg( P1(x) \vee ...
0
votes
1answer
67 views

Did I solve a basic derivation problem correctly?

The following problem is from "mathematical logic" by ian chiswell and wilfrid hodges, 2007.
0
votes
0answers
83 views

Which of the following statements is always TRUE?

Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE? $\left(\left(\forall x \left(P\left(x\right) \vee Q\left(x\right)\right)\right)\right) \implies ...
2
votes
1answer
39 views

Entails Propositional Logic

Is the following statement correct? if $ \alpha \models (\beta \vee \gamma) $ then $ \alpha \models \beta \vee \alpha \models \gamma $ or both. I guess it is, but how would you prove it?
1
vote
1answer
50 views

Proving a tautology

I need to prove that the deduction takes place: $$\frac{B\:\lor\:C,\:B\to \:A,\:C\to \:A}{A}$$ and I know how to do this using truth tables, but it specifically asks I use normal forms(Conjunctive ...
2
votes
1answer
72 views

Prove without using truth table

Prove that $$((p \lor q) \land (p \implies r) \land (q \implies r)) \implies r$$ is tautology without using truth table. My work so far: $$(\lnot p \land ¬q) \lor (p \land \lnot r) \lor (q \land ...
0
votes
1answer
52 views

Every teacher is liked by some student

What is the first order predicate calculus statement equivalent to the following? "Every teacher is liked by some student" $∀(x)\left[\text{teacher}\left(x\right) → ∃(y) ...
1
vote
3answers
40 views

Equivalence between fragments of intuitionistic and classical logics

Is the fragment $\{\vee,\land,\Rightarrow\}$ (no $\neg$) of intuitionistic propositional logic equivalent to the corresponding fragment of classical propositional logic, i.e. a formula is ...
0
votes
2answers
50 views

Proof that this equation is correct

Using a truth table I had no problems to proof, that this equation is correct. But how can I transform the first part to get to the second? I tried using de morgan but I never made it. Can anyone give ...
0
votes
0answers
22 views

Find truth value of propositional function

I have this propositional function: $p(x,y):y-x=y+x^2$ and I have to find truth value for: $\forall{x}\exists{y}$ $p(x,y)$ $\exists{y}\forall{x}$ $p(x,y)$ Set of all numbers is integer ...
1
vote
2answers
37 views

how to represent some sentences in propositional logic

HI does anyone know how to convert these two statements into propositional logic,?? 1."Any person can fool some of the people all of the time,all of the people some of the time,but not all of the ...
1
vote
1answer
39 views

Why not, first order logic to DNF conversion?

There seems to be huge amount of discussion about converting "first order logic to CNF". But don't see much about "first order logic to DNF" conversion. What is the reason?
1
vote
0answers
24 views

Explanation of $A \to B = \neg A \lor B$ [duplicate]

Can anybody explain intuitively why the logical implication $A \to B$ is equivalent to $$ \neg A \lor B$$ ? If e.g. $A$ is "It rains." and $B$ is "The street is wet.", then obviously $A$ implies ...
-1
votes
1answer
54 views

Pigeonhole principle formula using Propositonal Logic

According to the Pigeonhole Principle, if we try to place $n+1$ pigeons in $n$ pigeonholes, then at least one pigeonhole must have two or more pigeons. For $i \in \{1, 2, \dots, n+1\}$ and $j \in \{1, ...
2
votes
4answers
61 views

If $\{P \lor Q\} \land \{Q \implies R\}$ is true, does it follow that $\{P \lor R\}$ is also true?

If $$\{P \lor Q\} \land \{Q \implies R\}$$ is true, does it follow that $$\{P \lor R\}$$ is also true? Here is my attempt, using a truth table: $$ \begin{array}{ccc|c|c|c|c} P & Q & R & ...
1
vote
1answer
40 views

Is a tautology substitution instance with first order formulas valid?

I wonder how to show the following: Let $P_1,...,P_n$ be propositional symbols occurring in a tautology $\alpha$. Assume that $\varphi_1,...,\varphi_n$ are first order formulas and that $\alpha'$ ...
2
votes
1answer
43 views

How to negate the following proposition

If I have the the proposition: $\forall y, \exists x, \exists z [(Bx,y \wedge Rz,y) \vee (Bx,y \wedge Gz,y) \vee (Rx,y \wedge Gz,y)]$. (B,R and G are some other propositions but that doesn't matter ...
1
vote
1answer
33 views

Simple question about Paul Cohen's book “Set Theory and the Continuum Hypothesis”

On page 11 of section 4, under the heading Proof, Cohen writes: But $\neg A(c)$ does lead to a contradiction since $A(c)$ is valid and hence by Rule F so does $\exists x \neg A(x)$. I'm not sure ...
2
votes
1answer
27 views

prenex normal form and “free” variables

$∀Y ((∀Xp(X, Y )) → ∃Zq(X, Z))$ I am trying to convert the above formula into prenex normal form. I have done the following, but my answer seems to slightly differ from the correct answer: $∀Y ...
2
votes
2answers
25 views

Derive hypothesis in Propositional logic

I am learning to derive proofs of some sentences based on logical axiom schemes and inference rules. But there is a lot of unclear moments, like getting hypothesis. The one such example would be $A ...
0
votes
0answers
31 views

How to derive this equivalence in propositional logic (Xv!X)->(X->Z)v(Z->X)

I have no special skills of doing this. Can you introduce how to think of that ? I could take Xv!X as hip and then proof by parts x -> (X->Z)v(Z->X). But is the best way always to split disjunction ...
1
vote
1answer
42 views

A formula $\phi$ is logically equivalent to a another formula which contains only propositional variables and the connectives $\wedge$ and $\to$

Let $v_0$ be the valuation that assigns true ($T$) to every propositional variable. I'm trying to show that any formula $\phi$ is logically equivalent to one with only propositional variables and the ...
5
votes
1answer
103 views

Does double negation distribute over disjunction intuitionistically?

Does the following equivalence $$\lnot \lnot (A \lor B) \leftrightarrow (\lnot \lnot A \lor \lnot \lnot B)$$ hold in propositional intuitionistic logic? And in propositional minimal logic? (In ...
2
votes
1answer
29 views

Prove that $B ⇒ (C ⇒ D) ⊢ C ⇒ (B ⇒ D)$

I want to prove $B ⇒ (C ⇒ D) ⊢ C ⇒ (B ⇒ D)$ by the use of the following three axioms and modus ponens: $$(A1):(B ⇒ (C ⇒B ))$$ $$(A2):((B ⇒ (C ⇒D )) ⇒ ((B ⇒C ) ⇒ (B ⇒D )))$$ $$(A3):(((¬C ) ⇒ (¬B )) ...
0
votes
1answer
19 views

Define a proof system for propositional logic that uses truth-tables

I have been struggling with this question, and what I'm being asked to do. Defining a truth-table is (I think) fine: For any set of formulas Γ and formula φ, let us call the atoms of Γ, φ the ...
1
vote
2answers
33 views

prove $(p → r) ∨ ( q → r)$ logically equivalent to the statement $(p∧q) → r$

I came across this problem, it asks to use logical equivalences (see image), show that $(p → r) ∨ (q → r)$ logically equivalent to the statement $(p ∧ q) → r$ (aka definition of biconditional) After ...
2
votes
1answer
27 views

Logical formula deducing

I'm trying to find a way how to deduce a certain formula in Logical System which has only $(\lnot, \to )$ - negation and implication functions and these axioms: Ax1: $X\to (Y\to X)$ Ax2: $((X\to ...
1
vote
0answers
28 views

Show that the truth function $h$ determined by $(A \lor B) \implies \neg C$ generates all truth functions

Show that the truth function $h$ determined by $(A \lor B) \implies \neg C$ generates all truth functions. Could someone explain how I would go about proving this, or how I would start? I am having a ...
0
votes
0answers
20 views

Conversion into prenex conjunctive normal form

I'm trying to convert $\forall x \exists y(P(x, y) \rightarrow (\neg\exists z \exists yR(z, y) \wedge \neg\forall xS(x)))$ into PCNF, but am getting stuck at the end. $\equiv \forall x \exists y(\neg ...
1
vote
1answer
40 views

Modus ponens inference

I am looking to prove or disprove that the following formula; $(\neg A \rightarrow \neg B) \rightarrow (B \rightarrow A)$ can be inferenced in the following formal system $L(\neg, \rightarrow)$ ...
1
vote
1answer
63 views

Proving tautologies with $\iff$

I have a question regarding the process of proving that a statement form with $\!\iff\!$ is a tautology. For a simple example, let's say we have a statement: $ (A \iff (B\implies A))$ To attempt to ...
2
votes
2answers
39 views

Hilbert-style proof of $\Gamma\vdash\psi$ and $\Gamma\vdash\chi$ implies $\Gamma\vdash\psi\wedge\chi$

I am given the following Hilbert-style system (for intuitionistic propositional logic): Axiom schemes: $\phi\vee\phi\rightarrow\phi$ $\phi\rightarrow\phi\wedge\phi$ $\phi\rightarrow\phi\vee\psi$ ...
1
vote
1answer
44 views

First order logic,Step in Derivation of Non standard real numbers

This is from first order logic, specifically a section detailing the construction of the non standard real numbers, after Los' theorem And we have that:\ \ Let $L = \{+, ×, <, 0, 1\}$ be the ...
0
votes
1answer
21 views

Converting from DNF to CNF

How to convert a formula from DNF to CNF. Example: $(A \wedge \neg B) \vee (B \wedge \neg A)$ or similar trivial DNFs? It thought it could be work with the distributive law. But I don't know how to ...
3
votes
2answers
44 views

Derivation of $p \supset (\thicksim p \supset q)$ in Gödel's Proof by Nagel/Newman

The actual question I am currently reading Gödel's Proof by Nagel and Newman. Chapter V deals with the formalization and consistency of a simple system of formal logic. On page 50, after giving the ...
0
votes
1answer
50 views

Proof writing involving propositional logic: (p∧ (¬q) ) ↔ ((¬p) ∧ q) ≡ p ↔ q

Prove by using propositional logic: (p∧ (¬q) ) ↔ ((¬p) ∧ q) ≡ p ↔ q Is this possible? I tried solving but i get stuck. LS: = (p∧ (¬q) ) ↔ ((¬p) ∧ q) = ((p∧ (¬q) ) → ((¬p) ∧ q) ) ∧ ( ((¬p) ∧ ...
1
vote
4answers
60 views

Propositional logic - Natural deduction

I'm stuck with a big proof in my homework. I have to use natural deduction to prove something, and I think if I can prove this somehow then I can finish the full proof. Can anyone help? P v Q, ¬P : Q ...
0
votes
2answers
46 views

How to test CNF for satisfiability?

If we have a conjunctive linked expression where only the following clauses are allowed: $A_i, \quad \neg A_i, \quad A_i \vee \neg A_j, \quad \neg A_i \vee A_j$ Example: $A_1 \wedge (A_2 \vee \neg ...
0
votes
1answer
22 views

Propositional logic involving negation and if-statement: precedence

Quick help: So this is confusing me for some reason. I don't know what rule am i missing. I feel both should equal the same no matter how you start it. -(p → q) = (-p → -q) = (p ∨ -q) or -(p ...
2
votes
2answers
92 views

Is set of { AND , EXOR } gates functionally complete set?

Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function? XOR gates, NOT gates $2$ to $1$ multiplexers AND gates, XOR gates Three-input gates that ...
0
votes
3answers
59 views

A course on Logic.

I'm looking for a selection of books, in order to properly learn logic, starting from the most basic principles of propositional calculus and going up the ladder, up to higher order logic. My number ...