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
38 views

Natural deduction proof: {A → B, B → (C & D), ¬C v ¬D} ⊢ ¬A

$ 1- {A → B, B → (C \land D), ¬C \vee ¬D} ⊢ ¬A$ Our work (so far): $1- A → B$ $2- B → (C \land D)$ $3- ¬¬A$ $4- A$ $5- B$ (from 1,4) $→E$ $6- B$ $7- C \land D$ (from 2,6) $→E$ This is ...
2
votes
2answers
32 views

A Natural-Deduction proof of $ \{ \neg N,\neg N \to L,D \leftrightarrow \neg N \} \vdash (L \lor A) \land D $.

I would like to prove $\{ \neg N,\neg N \to L,D \leftrightarrow \neg N \} \vdash (L \lor A) \land D $. My work until now is as follows: $$ \begin{array}{l|ll} 1 & \neg N ...
-1
votes
3answers
39 views

Prove that the set of sentences $\{A \land (B \lor C), (\lnot C \lor H) \land (H \rightarrow \lnot H), \lnot B\}$ is inconsistent

Prove that the set of sentences $\left\{A \land (B \lor C), (¬C \lor H) \land (H \to \lnot H), \lnot B\right\}$ is inconsistent. I'm confused because it doesn't look like any of the forms I've ...
0
votes
1answer
39 views

Prove that the following argument is valid

I'm asked to show the following arguments are valid: P1) $[E \lor (L \lor M)] \land (E \leftrightarrow F)$ P2) $L \rightarrow D$ P3) $D \rightarrow \neg L$ C) $E \lor M$ Our work (so far): P2) ...
0
votes
0answers
45 views

Proof verification+proposition

Given 2 function $F(p,v)$ and $\frac{dF}{dv}=g(p,v)$ Differentiate F(p,v) with respect to v give $F_pf+F_v$ Formula 1 $$\frac{dF}{dv}=F_p\left(\frac{dp}{dv}\right)+F_v=g\\ ...
1
vote
3answers
59 views

Prove the two logic expressions are equal

Prove $\neg(a \lor b)$ is the same as $(\neg a \land \neg b)$ It makes sense when I think about it, but how does one prove it? Also is there a relationship with the above and saying: $(a \implies ...
1
vote
6answers
124 views

Why is $P \to Q \equiv \neg P \vee Q$?

By truth table, we know that $P \to Q$ is equivalent to $\neg P \vee Q$. But I'm trying to understand why this work? How can connective "or" be implication. I tried some examples but I still can't ...
4
votes
3answers
55 views

Logic: Can you drop parentheses in a conjunction?

In propositional logic, $p \land (q \land r) = (p \land q) \land r$ , where $p, q$ and $r$ are propositions. Does this mean $p \land (q \land r) = p \land q \land r$ ? If so, why?
1
vote
1answer
4 views

Consequence of compactness lemma

Let $\Gamma=\Sigma \cup \left\lbrace p_i,i\geq 1 \right\rbrace$ a countable set of propositional formulas. Assume also that for every boolean evaluation $u$ that maps every member of $\Sigma$ to true ...
0
votes
2answers
26 views

Negating statements with quantifiers in them

First statement, ∀ odd integers n, ∃ an integer k such that n = 2k + 1 Second statement, ∃ m ∈ ℝ such that ∀ n ∈ ℝ, m · n = n Before the negation, I'd like to ask tips on how to translate this ...
1
vote
2answers
23 views

What is the name of the Boolean function whose output is always one?

For example: f = a.b.c.d + !a.!b.!c.!d + a.!d + !a.b.!c + !b.d + b.c.d + a.b.!c.d + !a.c.!d = 1 ! is logical NOT, . is logiacal AND and + is logical OR. The ...
0
votes
4answers
38 views

Use tableau to convert formula to DNF/CNF form

Is there any method that can be used to convert any formula do a DNF/CNF form using only the truth table? For example if I have the following formula p → ¬(q∨r) How can I convert it into DNF? ...
0
votes
1answer
33 views

Logic : How to determine whether these propositions are contradictory ?

http://postimg.org/image/iips2lwdj/ The question asks to draw a truth table with the values of three propositions (linked), and following this, to "Show that the three propositions are ...
1
vote
3answers
312 views

Proving in a Hilbert system that $\neg A\Rightarrow A$ is a theorem, if assuming $\neg A$ makes it contradictory

Consider a Hilbert system $\mathcal{T}$ with modus ponens as the unique deduction rule, and subject to the following four axioms: For any relations $R,S$ and $T$ of $\mathcal{T}$, the relations ...
1
vote
1answer
28 views

Prove or disprove a sentence using HPC

according to HPC: Let S be a set of sentences and α that is not in S. Prove or disprove : If $S\cup\{\alpha\} \vdash \beta$ and $S\cup\{\neg \alpha\} \vdash \beta$ then $S\vdash \beta$. It ...
0
votes
1answer
54 views

Axiomatic proof - Mendelson system [closed]

How to prove $\neg \neg p \to p$ without having the premise $\neg \neg p$
3
votes
2answers
39 views

Write $(p↔q)$ in DNF

I have the following formula: $(p↔q)$ and I have to write in DNF (disjunctive normal form) This is where I got so far: $(p↔q) = ((p→q)∧(q→p)) = ((¬p∨q)∧(¬q∨p))$ but here I got stuck. How ...
1
vote
1answer
35 views

Every positive formula is satisifiable

We say that a propositional logical formula is positive if it does not include the negation connective ¬ anywhere in it (but it may still use ∧, ∨, ↔, →, and propositions). Show that all ...
1
vote
2answers
22 views

Proving that a set with a quaternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{N\}$ of one logical connective is inadequate where $N$ is a quaternary connective that is defined as follows: $N(w,x,y,z)=((x\land y)\land(w\lor z))$ ...
2
votes
1answer
57 views

Argue that if a sentence has a proof, then it is a tautology

This is a corollary of the soundness theorem, which states that for a set of formulas $\Phi$ (of propositional logic) and a formula $\alpha$ : $$\Phi\vdash\alpha\Longrightarrow\Phi\vDash\alpha$$ What ...
2
votes
1answer
27 views

Question regarding using the natural deduction system

I have the following: Premise: ((V → ¬W) ∧ (X → Y)) Premise: (¬W → Z) Premise: (V ∧ X) |- (Z ∧Y) The part I want to know is how do I go about separating ...
1
vote
1answer
31 views

Equivalence of two biconditionals of propositional metalogic

In application to propositional metalogic, I am told that the following two biconditionals are equivalent: (i) Γ is satisfiable iff every finite subset of Γ is satisfiable. (ii) Γ ⊨ α iff some ...
0
votes
1answer
76 views

Disjunctive normal form and shannon normal form

Consider the formula (( true | (a <-> b)) & ((c | b) ^ a ^ b)). transform the formula into disjunctive normal form for the variable ordering a ≤ b ≤ c ≤ d. Also transform to Shannon normal form ...
0
votes
0answers
22 views

Construction of atomically closed tableu from a closed tableu

Suppose we have a closed tableu with at least one branch $\theta$ that contains $X$ and $\neg X$ where X is non-atomic formula. My strategy could be that of exploring the cases of X being an ...
3
votes
1answer
50 views

What is the set of propositional formulas?

What is the set of propositional formulas? I am not sure if I understand this
0
votes
1answer
54 views

Complete operator base logic [closed]

Show that $F={0,\to}$ is a complete operator basis by giving equivalent formulas for negation,conjunction and disjunction over F.
-3
votes
4answers
31 views

Propositions problem [closed]

For any two propositions p and q show that $\sim (p \vee q) \equiv \sim p \wedge \sim q $ Do please any body explain that question as well as give the answer?
1
vote
4answers
64 views

Filling in a missing portion of a truth table

I have the following truth table: $$ \boxed{ \begin{array}{c|c|c|c} a & b & c & x \\ \hline F & F & F & F \\ F & F & T & F \\ F & T & F ...
3
votes
1answer
70 views

Satisfiability proof of formulas with pure literals

Let $\varphi$ be any propositional formula in negation normal form (NNF). A literal $\ell$ is pure in a formula $\varphi$, if the complement of $\ell$, $\ell^c$, does not occur in $\varphi$, where ...
1
vote
1answer
444 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
3
votes
6answers
414 views

'If you neglect your homework, then you’ll fail': Can it be expressed as $P \vee \lnot Q $?

Source: p 46, How to Prove It, by Daniel Velleman Please beware that although the author writes the original apodosis as 'You’ll fail the course', I shorten it to 'You'll fail', for convenience. ...
6
votes
5answers
449 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$?
1
vote
1answer
41 views

Prove that the intersection of definable sets is definable

Hello I have a question : $F$ is a family of definable sets. Prove that the intersection of all the sets in the family is definable. ($F$ could be infinite) Definition (Definable): a set $K$ of ...
1
vote
1answer
49 views

Find indefinable set that is included in definable set.

Find $K\subseteq \operatorname{Ass} $ and $ K'\subseteq K$ such that $K$ is definable but $K'$ is not. Definition (Definable): a set $K$ of assignments is definable if there is a set of formulas A ...
2
votes
1answer
80 views

I'm wodering if this statement is provable in logic $ \lnot \alpha \to \lnot \lnot \lnot \alpha ) $

I've encountered this statement in my final exam $$ \lnot \alpha \to \lnot \lnot \lnot \alpha ) $$ there was no open parenthesis and from what I know this is invalid (not a well-formed formula) so ...
10
votes
4answers
615 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.
2
votes
2answers
45 views

Propositional Calculus, Can someone answer the following?

Can somebody please solve the following equations: \begin{align} 1. \quad (A \rightarrow B)\land (A\rightarrow \neg B)=\lnot A \quad \quad \\ \end{align} What I have got for it so far is ...
2
votes
3answers
63 views

Solving this logical puzzle by resolution doesn't work for me

In this document there is a logical puzzle: If the unicorn is mythical, then it is immortal. If the unicorn is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a ...
2
votes
4answers
78 views

How to prove this tautology using equivalences?

I am trying to prove that the following is a tautology: $(A \implies (B \implies C)) \implies ((A \implies (C \implies D)) \implies (A \implies (B \implies D)))$ To make progress, I thought I'd ...
3
votes
3answers
90 views

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. Is this valid?

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. I would say that this is false since the weather isn't directly influencing John's health. Am I right or wrong? Should I use ...
3
votes
4answers
128 views

Proving $ \neg ( \neg \alpha \wedge \neg \neg \alpha )$

I'm training to prove this statement , but first I need to know if this statement can be proved in : 1 - both in classical and Intuitionistic logic ( in this case i need to provide demonstration in ...
6
votes
2answers
109 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 ...
2
votes
1answer
48 views

Proving that a set with a ternary logical connective is functionally incomplete (i.e. inadequate)

I am stucked at trying to prove that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its arguments are $T$. For example: ...
0
votes
2answers
3k views

How can I prove [P->(Q->R)] is equivalent to [(P^Q) ->R]

I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have ...
3
votes
1answer
123 views

Proving that a propositional theory of any cardinality has an independent set of axioms

This is exercise 1.2.19 from Chang & Keisler's Model Theory, which has been giving me a headache for some time now. Let $\mathscr{S}$ be a given propositional language of any cardinality (i.e. ...
3
votes
1answer
37 views

Prove that ≿ is transitive iff ≻ and ∼ are transitive

Let ≿ be a complete preference relation (as in game theory). How to prove that ≿ is transitive if and only if ≻ and ∼ are both transitive? My reasoning is as follows. ...
-1
votes
2answers
85 views

Simplifying on logic Operations

I need simplify the following proposition to 2 logic operations using the laws of the algebra of propositions. Write each step on a separate line with the algebra law you used as a justification. ...
0
votes
1answer
47 views

I am trying to use proof of sequence correctly to make valid

Here I am trying to use a proof sequence so that the argument is valid (hint: the last A’ has to be inferred). (A → C) ∧ (C → B') ∧ B → A' Here are my steps I tried but not sure if this is correct ...
8
votes
6answers
2k 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: ...
1
vote
1answer
44 views

How to evaluate the single turnstile symbol ($\vdash$) in propositional logic?

Wikipedia says, that: $x \vdash y$ means y is provable from x (in some specified formal system). But what do you actually check or calculate, when you have $(a \land \lnot b) \vdash a$? Has $(a ...