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
1answer
184 views

Confused about proof by contradition

In proof by contradiction, I can understand how it works when the hypothesis leads to a clearly false proposition. e.g., if we want to prove $P$, we assume $\neg P$ and show that $\neg P \implies ... ...
0
votes
1answer
42 views

How to solve this propositional logic propblems using the following rules.

Okay so I have the following problem, which I need to solve without using truth tables. This is the formula p ∧ (¬p ∨ q) ≡ p ∧ q and these are the semantic ...
1
vote
2answers
51 views

how to prove the following formula true using semantic equivalences

Hi I am trying to prove the following the formula and this is what I have so far false ∨ p ≡ p This is what I have do so far ...
0
votes
1answer
44 views

Proving inadequacy given a set of connectives

Let $\oplus$ be a binary connective defined by the truth table: $\begin{array} {|r|r|} \hline p &q & p \oplus q\\ \hline 0 &0 &0\\ \hline 0 &1 &1\\ \hline 1 &0 &1\\ ...
0
votes
2answers
40 views

How can I prove the following formula using semantic equivalences

Hi I am trying to prove the following formula using semantic equivalences $$(p \land q) \to r \;\equiv\; p \to (q \to r )$$ I am thinking maybe to use the implication rule but I am note sure.
1
vote
3answers
52 views

Verify if Propositions hold or not

I want to show wether or not these two propositions hold or not. The first one is that $$\forall x\exists y(xy>0\implies y>0)$$ For this one I noticed that hen $y=0$ it doesn’t hold. But I’m ...
0
votes
0answers
14 views

Find algebraic normal form that's derived from 2 other ANF

I have to find the ANF of a function $h$ where $h = f \star g$ where $x \star y := x \wedge \neg y$. $f$ and $g$ are given functions. They are $f(x, y, z) = y \oplus x \oplus xy \oplus zy \oplus zx ...
0
votes
1answer
54 views

Tarski's semantic conception of truth and logic

Tarski's semantic conception of truth states: $X$ is true iff p (where $p$ is a sentence, and $X$ is the name of the sentence $p$ to which the truth predicate applies). However, in logic, to express ...
1
vote
1answer
40 views

Proof of Why or Why Not some equivalence holds

How do I prove that this equivalence $$\lnot\exists x\,\forall y\,(P(x)\Rightarrow\lnot Q(x,y))\equiv \forall x\,\exists y\,(P(x)\land Q(x,y))$$ holds or not? I remember that $A\implies B\equiv\lnot ...
0
votes
2answers
27 views

I cannot figure out what this question means with the semantic turnstile

Hi I have recently started studying propositional logic and am finally understanding the truth tables and how to use them. I came across this formula which is confusing me. Use truth tables to ...
0
votes
1answer
54 views

DNF simplification

I am currently learning about propositions and logical equivalences in a mathematics course I'm taking at university. I'm having trouble understanding how to simplify DNF Formulas. I was given a truth ...
0
votes
0answers
113 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
35 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
30 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
34 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
46 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
33 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
98 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
21 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
38 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
49 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
53 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
57 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
31 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
41 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
66 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
44 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
36 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
46 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
40 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
41 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
2answers
52 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
23 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
54 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
30 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
61 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
55 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
38 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
27 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
33 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
47 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
70 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
49 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
33 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
60 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 ...