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)

0
votes
0answers
110 views

Is the establishment of the validity of this argument correct?

I am trying to show that the following argument is valid. There is an email that is sent but it is not saved in the inbox. All emails are saved in the inbox or the inbox is full. If the inbox is ...
0
votes
1answer
31 views

Propositional Equivalence

Are the following two propositions equivalent? p IMPLIES (q IMPLIES r) p IMPLIES (q AND r) From what I can tell, using the logical equivalences, this should be false, correct? p ...
0
votes
1answer
27 views

which of the following are valid propositions?

Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE? 1.((∀x(P(x) ∨ Q(x)))) ⟹ ((∀xP(x)) ∨ (∀xQ(x))) 2.(∀x(P (x) ⟹ Q (x))) ⟹ ((∀xP(x)) ⟹ (∀xQ(x))) 3.(∀x(P(x)) ...
0
votes
1answer
25 views

Propositional Logic - Resolution Strategies

I need help understanding these resolution strategies. 1) Set of support 2) Linear input Let's assume $\mathcal{S} = \{ C_1, ... ,C_n\}$ is our set of clauses. and we want to derive / prove ...
0
votes
1answer
39 views

Proof strategy for propositional logic algorithm

I have to proof the following theorem: Proof that $\eta_1 \vee \eta_2 \equiv DISTR(\eta_1, \eta_2)$. The algorithm DISTR($\eta_1, \eta_2$) is the following: Now I want to use induction to ...
2
votes
1answer
32 views

Verification of proof of propositional logic

I made a proof for the following theorem. But I'm not completely certain that it's fully correct. Suppose $\phi$ is a propositional formula and that the two evaluations $v$ and $w$ are equal for ...
1
vote
3answers
78 views

Propositional Logic- Prove sentences (a) and (b) entail (c)

I'm given three sentences: (a) If Frodo destroys the ring, then the world will be saved. (b) Gollum stole the ring from Frodo or Frodo destroyed the ring. (c) The world will be saved or Gollum stole ...
0
votes
1answer
17 views

Reducing propositional logic statements

I am having some trouble with reducing some propositional logic statements. The first one is as follows: $\neg(P \lor Q) \lor \neg (P \lor \neg Q)$. I used deMorgan's law to change this to: ...
0
votes
1answer
34 views

Verification of Lindenbaum's Lemma proof for the Mendelson system and a question of maximally consistent sets.

In this proof I will use Mendelson's axiom system (the one in this book). Question 1: Could someone check my work? I feel some parts are a bit hard to see/read, but I think the general idea ...
1
vote
0answers
22 views

Question in regards to representing propositons with P/~P

In a standard Frege-System does it break any rules to have 'P' stand for, say "Smith is not president"? Is it mandatory that such a statement be represented by '~P', or can it indeed be represented ...
0
votes
1answer
47 views

writing a formal proof

If B is a statement form involving only negation, conjunction and disjunction, and B' results from B by replacing each conjunction by a disjunction and each disjunction by a conjunction, show that B ...
0
votes
2answers
46 views

Proving that if $\Gamma \cup \{\gamma\}$ is inconsistent, then $\Gamma\vdash \neg\gamma$.

Definition Let $\gamma\in \text{Form}$. A proof of $\gamma$ is a sequence of formulas $\phi_1,\phi_2,...,\phi_n=\gamma$ where each $\phi_i$ is an instance of an axiom or was obtained by modus ponens ...
0
votes
1answer
52 views

Proof of the deduction theorem explanation

I'm reading through this proof of the deduction theorem, and there are a few things I don't understand. The basic idea is to show that if $\Gamma\cup \{A\}\vdash B$, then we have a proof of $B$ with ...
1
vote
1answer
25 views

If a set $S$ is inconsistent, does $S\vdash \alpha$ for all $\alpha$ in this system?

Let $S$ be an inconsistent set of propositional formulas. If our system consists of the axioms: \begin{align} AX1&\quad (P\implies (Q \implies P))\\ AX2&\quad (((P\implies(Q\implies ...
0
votes
1answer
38 views

Completeness of Propositional Logic: Help understanding a proof.

I'm reading through wikipedia's proof of the completeness of propositional logic and I'm having trouble understanding the last parts of the proof: At part III, why is "if $G^*$ contains $C$ and ...
0
votes
3answers
36 views

Equivalence between “a iff b” and “(a → b)^(b→a)”

so I have gotten a bit lost on this. "a iff b" suggests to be that "a" can be the case only if "b" is the case so that having "a" be true and "b" be false would be contradictive. From this line of ...
0
votes
1answer
64 views

Proof in Propositional Logic of Peirce's Law

How can I proove in Propositional Logic (using only the basic axioms of P.L. and not a valuation function like it's used in Propositional Calculus) that : $\vdash$ ((($\phi$ $\to$ $\psi$ )$\to$ ...
0
votes
1answer
37 views

Can someone break this Propositional logic formulae down for me via truth table

This is my first day learning about logic and logic programming, I have been doing some exercises using a truth table for propositional logic questions ...
0
votes
1answer
31 views

How is the following an equivalent proposition?

I am taking a discrete mathematics course and one of the questions asks to develop an English translation of a proposition. The proposition has the following structure [Question 9 part H is where I ...
1
vote
1answer
41 views

Proving that a set is not consistent

Ok so i was given the following problem: if $\Sigma \vdash \psi $ then the set $\Sigma\cup${$\lnot\psi$} is not consitent .Prove it by using only the theorems of completeness and correctness which ...
0
votes
1answer
33 views

Proving a Tautological implication in logic

Ok so we are asked to prove the following: $\Sigma \cup\phi\vDash\psi$ if and only if $\Sigma\vDash\psi\rightarrow \phi $ where $\Sigma$ is a set of types(not empty set), and $\phi$ and $\psi$ are ...
0
votes
1answer
40 views

Confused about implications and basic logic : A problem with $\lor$ and a contrapositive

Suppose I have a generic function $f$ that satisfies $$\frac{f(a)}{b} + \frac{f(b)}{a} = \frac{f(a)}{a} + \frac{f(b)}{b}$$ for some $a$ and $b$ in the domain of $f$, with $a \neq b$. Assume further ...
0
votes
3answers
49 views

How can I further simplify (P ∨ ¬Q) → ¬(P ∨ Q)?

I am trying to simplify this equation, (it was more complex before the current point), but I'm stuck at this juncture, and am not sure where to go from here. I've used De Morgan's Law and the Rule of ...
2
votes
1answer
17 views

Proposition logic resolution proof

Given a knowledge base $$ P \vee Q, R \implies \neg Q, \neg R $$ I have to prove that $$KB \models P \wedge \neg R$$ is FALSE through model checking.. I derived $$ \neg P \implies Q $$ $$ Q ...
4
votes
1answer
51 views

Write formulas in specific languages of group.

So, for each of the following groups write a formula in the language of group theory, which holds in given group, but doesn't hold in others two. $(i)$ The integers with addition \ I think it's ...
2
votes
0answers
27 views

Compactness Theorem (Propositional Logic) and Compactness (Metric spaces). [duplicate]

Definition. A subset $E$ of a metric space $(X,\tau)$ is compact if every open cover of $E$ has a finite subcover. Theorem (Compactness Theorem). A set $\Gamma$ of formulas is ...
0
votes
1answer
27 views

Boolean Problem Simplification

I am trying to simplify the boolean function F= ~A~BC + A~B~C + A~BC + AB~C + ABC and I know that correct answer is F= A + ~BC. My attempt is: ~A~BC + A~B(~C+C) + AB(~C+C) ~A~BC+ A(~B+B) ~A~BC + A ...
0
votes
2answers
59 views

Does function: $ f: \mathbb{Z} \to \mathbb{Z} $ exist for these statements

Does function: $ f: \mathbb{Z} \to \mathbb{Z} $ exist, such that this statement is true: $$(\forall{x} \in \mathbb{Z}:f(x) \geq 2)\Rightarrow(\forall{x}\in \mathbb{Z}:f(x)<10)$$ and this statement ...
1
vote
2answers
32 views

Simplify Implication Expression (Predicate/Prop Logic)

I'm trying to do some past paper questions for revision and find myself perplexed on some of the expressions that need normalized/simplified which involves an implies. For example: (A ∧ ¬B) → B ∨ C ∨ ...
1
vote
0answers
35 views

Soundness of Propositional Logic proof.

Let $$\begin{align} A1&=(p\implies (q\implies p)) \\ A2&=(((p\implies (q \implies r)) \implies ((p\implies q)\implies (p\implies r))) \\ A3&=((\neg p \implies \neg q ) \implies ((\neg p ...
1
vote
0answers
24 views

“Relative unsatisfiability” of SAT instances

There's a natural way to view any SAT instance as a variety: just replace the Boolean algebra $2$ of truth values with the corresponding Boolean ring $\mathbb{Z}/2\mathbb{Z}$. (See my answer to Is ...
0
votes
1answer
24 views

Proof of Generalized Distributive Laws by mathematical induction

Prove the following Generalized Distributive Laws. p∧(${q_1}$ $\lor$ ${q_2}$ $\lor$...$\lor$ ${q_n}$) ⇔ (p$\land$ ${q_1}$)∨(p$\land$ ${q_2}$)∨....∨(p$\land$ ${q_n}$) My attempt When n=1, the ...
0
votes
1answer
25 views

Valid Arguments

If i have the following arguments : \begin{align} & a \to (b \lor c)\\ & \lnot b \lor \lnot c \\ & c \lor a \\ & --- \\ & b \end{align} How do i prove that its valid. My ...
1
vote
1answer
43 views

What can we do with Propositional Logic?

I've studied a bit of propositional logic and first order logic, I know that propositional logic is sound and complete ($\Gamma \vdash \gamma$ if and only if $\Gamma \vDash \gamma$), I know what ...
1
vote
0answers
43 views

Relations between statements involving universal quantifier, conditional and biconditional

If we consider two predicates: $b(x)$: x is a boy $c(x)$: x is clever Then, there are four statements involving $∀, b(x), c(x), →$ and $↔$ . These are below along with my interpretation of their ...
0
votes
1answer
53 views

proof of Generalized De Morgan's Laws by mathematical induction

Mathematical induction: Prove the following Generalized De Morgan's Laws. $\sim({p_1\land p_2 \land \cdots \land p_n}) \iff \sim{p_1}\lor\sim{p_2}\lor\cdots\lor\sim{p_n}$ My attempt: I'll use ...
2
votes
1answer
43 views

Turning CNF into DNF

I have a formula $(L\Leftrightarrow (A\vee J))$ and I am to turn it into DNF and CNF. When I use de Morgan rules and so on, the formula looks like $(L\Rightarrow (A\vee J))\wedge ((A\vee ...
2
votes
2answers
31 views

How to represent some logical propositions

How can I logically represent the following propositions: At most one of $p$,$q$,$r$. Only one of $p$, $q$, $r$. My solutions: ($p$ and ~($q$ or $r$)) or ($q$ and ~($p$ or $r$)) or ($r$ and ~( ...
1
vote
1answer
42 views

Resolution refutation with biconditional

I was referring to this MIT OCW slides to learn about resolution refutation. Recently I came across following problem: Check if following is tautology $(a\leftrightarrow c)\rightarrow (\lnot ...
1
vote
2answers
43 views

Interpreting resolution rule of inference

I know that the the resolution rule of inference states that $(p \lor r)\wedge (q \lor \lnot r) \to (p \lor q)$ Based on this, my textbook says that below statement is true: $(p \vee q)$ is ...
0
votes
1answer
32 views

Generating truth tables for quantifiers online

Is there any online tool that can generate truth tables for quatifiers (existential and universal). I can generate for Boolean equations not involving quantifier as this one? But I didnt find any ...
0
votes
1answer
50 views

Checking validity of propositional statement

I was unable to solve this particular problem which asks to find the valid first order logic among below: $\forall x(P(x)\to Q(x))\to (\forall xP(x)\to\forall xQ(x))$ $\exists x(P(x) \lor Q(x))\to ...
0
votes
2answers
23 views

Proving resolution inference rule without truth table

I came across resolution inference rule stating: $((p\lor q)\land (\lnot p\lor r))\rightarrow(q\lor r)$ I googled a lot but what I get is either the proof using truth table or using this to ...
3
votes
2answers
60 views

How to translate“If $X$ then $Y$ unless $Z$” to propositional logic.

As the title says, the given sentence is If $x$ then $y$ unless $z$" Now according to my learning "If $x$ then $y$" translates to: $x\rightarrow y$. Also according to Kenneth Rosen's book ...
3
votes
2answers
22 views

Unrecognized application of absorption

I got stuck on a proof on a test at the following step: $$\neg p \wedge (r \vee\neg p)\wedge (r \vee\neg q)$$ And my professor transformed this to: $$\neg p \wedge (r\vee\neg q)$$ And he justified ...
6
votes
1answer
143 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 ...
3
votes
2answers
65 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
52 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
130 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
41 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 ...