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)

3
votes
2answers
70 views

Who is the culprit?

" Andy says: "Cindy is guilty". Bart says: "I am not guilty". Cindy says: "Danny is guilty". Danny says: "Cindy lies if she says I am guilty". We know there is exactly one guilty person and ...
1
vote
3answers
60 views

Proving $(A \implies B) \land (\lnot A \implies C)~,~~ (A \implies \lnot B) \land (\lnot A \implies C) \vdash C$?

Just to let you know - This is an assignment, so I wouldn't like a full answer - just some hints :) I am required to prove the following: $$(A \implies B) \land (\lnot A \implies C)~,~~ (A ...
0
votes
1answer
165 views

Does Superman exist? (Logical analysis)

I am given as exercise to check the following reasonment: "If superman is able to and wants to prevent evil, he will. If superman is not able to prevent evil, then he is passed out. If superman ...
0
votes
2answers
46 views

Propositional formulas 3

What are the difference between: $A \implies (B \implies C)$, $\ (A \implies B) \implies C$, $\ A\land B \implies C$, $\ A \implies B \land C$, $\ (A \implies B)\land (B \implies C)$? Why we can not ...
3
votes
1answer
56 views

If $\Gamma$ is an infinite set of propositional formulas, is the statement: “$\Gamma$ is satisfiable” decidable?

Here, $\Gamma$ is satisfiable means that there exists a truth function $v$ such that $v(\gamma)=$ True for all $\gamma \in \Gamma$. I know that the set of all propositional formulas is countable (our ...
0
votes
3answers
52 views

Prove [(q ˄ (p ↔ ¬ q) ) → q] is a tautology using logic laws

How to prove that this statement is tautology using logic laws (q ˄ (p ↔ ¬ q) ) → q Edit: I got stuck here after trying to apply De Morgan's law: ...
0
votes
1answer
36 views

Let $S$ be any set of statements. How do I concisely show that $\sim$ is reflexive, symmetric, and transitive on $S$?

The following problem is exercise 2.5.2 from "Mathematical Logic" by Ian Chiswell and Wilfrid Hodges (2007). I feel that the part about symmetry and transivity is a bit verbose and somewhat clumsy. ...
1
vote
1answer
44 views

Show that a set of connectives {∨, ∧} through structural induction is not a complete set of connectives

I understand how a set of connectives such as {∨,∧,¬}, can be considered adequate, but I'm not fully understanding how one would go proving something that is not adequate The full problem is as ...
1
vote
1answer
59 views

For a homework, how do i use resolution to prove G

$F_1 = ∀x∃y \, R(x,y)$ $F_2 = ∀x \, (∀y \, R(x,y) \to ∃z \, S(x,z))$ $F_3 = ∀x∀y∀z \, (R(x,y) \to (S(x,z) \to S(y,z)))$ $G = ∀x∃y \, S(x,y)$ Using resolution show that $F_1,F_2,F_3 \models G$. So ...
0
votes
1answer
31 views

If $P \lor Q$ and $\neg P \lor \neg Q$ are both true, do we get a contradiction?

Question If $$P \lor Q$$ and $$\neg P \lor \neg Q$$ are both true, do we get a contradiction? My Attempt Since $$\left\{\neg P \lor \neg Q\right\} \Longleftrightarrow \neg \left\{P \land ...
1
vote
1answer
92 views

Is this (tricky) natural deduction with De Morgan's laws correct?

Just a practice question, however just wondering if this ND proof is correct? I have put brackets in 2.2 and not in 2.3 however this shouldn't make a difference?
0
votes
1answer
55 views

Prove that $K$ is finitely definable iff $K$ has finite support

Hi guys I need to prove a Finite Support Theorem which states that $K$ is finitely definable iff $K$ has finite support. Unfortunately I succeeded in proving only the first part of if and only if. ...
0
votes
2answers
34 views

(Propositional logic): Can I do a conjunction in the antecedent of a conditional

Can I do a conjunction in the antecedent of a conditional? i.e. step 7 in my derivation below legit? $A \rightarrow B\qquad\qquad$ (Premise) $A \rightarrow C\qquad\qquad$ (Premise) $A ...
0
votes
2answers
52 views

Is it possible for there to be a mechanical way in which one would prove a tautology (in a propositional calculus)

Basically is there any algorithm for proving a tautology? (even if it runs in exponential time?) Additionally, is it possible for a propositional calculus to be such that a tautology is presented in ...
1
vote
1answer
31 views

Describe which partial orderings yield boolean algebras

I thougt about propositional logic and boolean algebras and how propositional logic is (at least from one point of view) not really about $\land,\lor,\neg,...$ but about boolean operators, i.e. n-ary ...
0
votes
0answers
33 views

How to apply Rules of inference

I know the definition for Rules of inference "A rule of inference is a general pattern that allows us to draw some new conclusion from a set of given ...
1
vote
1answer
60 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
59 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
37 views
2
votes
1answer
28 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
74 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
56 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
54 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
21 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
501 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
24 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
70 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
129 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
69 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
93 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
59 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
47 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
51 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
23 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
58 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
44 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?
3
votes
1answer
37 views

“Relatively” functionally complete connectives

The Sheffer stroke (https://en.wikipedia.org/wiki/Sheffer_stroke) is functionally complete: any truth-functional connective (such as $\wedge, \vee, \rightarrow$, . . .) can be represented purely in ...
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
78 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
49 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
45 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
34 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
33 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
30 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
34 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
45 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 ...
1
vote
1answer
40 views

What is the order of precedence to $\Gamma \vdash \phi \Rightarrow \psi$?

In this context, $\phi$ and $\psi$ are formulas and $\Gamma$ is a set of formulas. I'm not quite sure what it means. Does it mean $\Gamma \vdash (\phi \Rightarrow \psi)$ or does it mean $(\Gamma ...
5
votes
1answer
120 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 ...