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
3answers
105 views

Fitch-Style Proof

Hi I'm having trouble solving a Fitch Style Proof and I was hoping someone would be able to help me. Premises: $A \land (B \lor C)$ $B \to D$ $C \to E$ Goal: $\neg E \to D$ Thank You
1
vote
3answers
81 views

prove validity of following sequent

How to prove validity of following sequent using rules of conjunction, disjunction, implication, negation etc. Premises: $ c \wedge n \Rightarrow t$ , $h \wedge \sim s$, $h \wedge \sim(s\vee c) ...
1
vote
2answers
231 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: $(R\lor R)\Rightarrow R$. $R\Rightarrow (R\lor S)$. $(R\lor ...
1
vote
2answers
88 views

Circuit Logic NAND

I have to build a circuit using only NAND gates. But I wasn't given an equation. Instead I was given this formula: F(wxyz)= E m(0,1,2,3,4,5,7,14,15) Function of (wxyz) = Sum m(0,1,2,3,4,5,7,14,15) ...
0
votes
2answers
45 views

Definition nested and unnested first order formulas

What's the definition of nested and unnested formulas in a first order language? I came across the term in a model theory book i'm reading, and I can't seem to find it defined there, or in my brief ...
0
votes
2answers
66 views

Convert this solution to inference notation

This is a proof for De Morgan's Law. Could you help me convert this to inference notation so I can understand the proof better? I find it hard reading this, specifically, which line each assumption ...
4
votes
1answer
140 views

What are those “things that cannot be proved using only ordinary rules of inference”?

The online edition of the book Introduction to Logic by Michael Genesereth and Eric Kao, has a detail that left me confused. CHAPTER 4 [...] 4.2 Linear Proofs [...] The ...
1
vote
1answer
60 views

Mathematical Logic Past Paper Question: n is a positive integer, $X_n$ = ${(x_1,.,x_n) : x_i ∈ {T,F}}$ is the set of n- tuples from {T,F}.

Suppose $n$ is a positive integer and $X_n = \{(x_1,\ldots ,x_n) \colon x_i ∈ \{T,F\}\}$ is the set of $n$- tuples from $\{T,F\}$. Suppose $f\colon X_n \to \{T,F\}$ is a function and $f(x) = T$ for ...
1
vote
1answer
49 views

formal proof - logic

I am trying to prove the following, using natural deduction: $$p\wedge q\Leftrightarrow p \vdash p \Rightarrow q$$ with the following but i seem to get stuck. I know i have to prove $q$, but am not ...
1
vote
1answer
100 views

Discrete math proof issue

This is a question from my discrete math quiz. I was asked to prove there exists a Q(x). I used Disjunctive Syllogism to prove it. I was marked incorrectly because I used two different variables in ...
1
vote
1answer
338 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.
0
votes
1answer
16 views

Conversion of disjunctive normal form to conjunctive normal form

Explain how $ (p \lor q \lor r \lor s) $ can be re-written into an equivalent CNF formula such that each clause contains exactly $3$ variables or negations of variables.
0
votes
1answer
21 views

Is my interpretation of these propositional formulas correct?

We define two propositions P and Q as follows. P: Victoria studies hard for the final exam. Q: Victoria desperately wants to ace the final exam. (a) Translate each of the following statements into ...
0
votes
1answer
47 views

exclusive or logic truth table - not understanding why it is the way it is

In terms of logic and truth tables why is it that the truth table for exclusive or is as follows: Consider $P$ and $Q$. Let $P + Q$ denote exclusive or. Then if $P$ and $Q$ are both true or are both ...
0
votes
1answer
34 views

Can an arbitrary formula in propositional logic be converted to 2CNF, preserving equivalence?

Suppose I have an arbitrary formula $\Phi$ in propositional logic. Is there a way to convert $\Phi$ to a 2-CNF formula $\Psi$ such that $\Phi \equiv \Psi$? If not, why not?
0
votes
1answer
32 views

2 Distinct Bijective functions

I have that A is a set of $2k^2$ so it equals $\{2,8,18,32,50...\}$ How do you Construct two distinct bijections $f, g : \mathbb{Z}^{+} \to A$. I was able to get $f(x)=2x^2$ what would $g(x)$ be? ...
0
votes
1answer
102 views

Solving box proofs problem

I'm trying to solve this box-proof puzzle but I don't understand how to complete it as I need to somehow assume $A0$ or $\neg\neg B2$. I've used a truth-table solver to confirm that this is a ...
0
votes
1answer
35 views

Complete recursively Set

The set $\Sigma=\{ p_1\rightarrow p_2, p_2\rightarrow p_3, ... \}$ Is it complete? why? Is it recursively axiomatizable? Why? Is the consequences of this set recursive? Why? Thanks so much.
0
votes
1answer
24 views

Where to start when converting a logical formula to English?

I've got this problem with some atomic sentences, I was just wondering whether when converting it into English I needed to do the brackets first along with precedence or whether I just work my way ...
0
votes
1answer
49 views

Are the conditional connectives necessary in the following statements?

Here is a question from my book that I'm studying from: Analyze the logical form of the following statement (a)Everything in that store is either over priced or poorly made. (b)Some ...
0
votes
1answer
55 views

Cardinality of Distinct Hilbert Systems with Detachment

Let us consider all formulas T of classical propositional logic which are tautologies up to simple substitution of variables where a variable can get simply substituted for another variable if and ...
3
votes
0answers
38 views

Proving a graph has a property if all finite subgraphs have that property

Given a graph $G=(V,E)$ and an integer $k\in\mathbb N$, we will say that $G$ is $k$-good if: for every division $V=\bigcup_{i\in I} U_i$ such that $i\not=j \Rightarrow U_i\cap U_j =\emptyset$ and ...
3
votes
0answers
66 views

Application of the compactness theorem

In my logic book they ask me to prove the following as a consequence of the compactness theorem for propositional logic. Let $S \subseteq N$ be an infinite set. I have to show that there exists an ...
3
votes
0answers
139 views

meaning of ``partial converse''

In the definition of a commutative ring $(R,+,\times)$, one of the postulates given is that of uniqueness, i.e. that $$ a=a', b=b'\implies a+b=a'+b', ab=a' b'.$$ The text states that for the system ...
3
votes
0answers
59 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
3
votes
0answers
305 views

Constructor And\Or-graph on function transition of the alternating automata

In a And\Or-graph induced by the transition function, each node of G corresponds to a state q belonging to set Q of the state of the Automaton, for q with $\delta(q,a)=q1*q2$, the node is a $*-node$ ...
2
votes
0answers
37 views

Proposition into spoken language

Given: $\sim( p \leftrightarrow (q \vee r) )$ $p:$ It's raining $q:$ The sun is shining $r:$ There are clouds in the sky. Translate the proposition into spoken language. ...
2
votes
0answers
72 views

Does There Exist A Fourth Independent Axiom Here?

I use Polish notation. The implicational calculus of propositions under detachment and uniform substitution has the following axioms as a basis: ...
2
votes
0answers
43 views

Expressing schedule of reinforcement rule using mathematical logic

I am trying to formalize the rules for application of different schedules in a reinforcement learning in special education. Children learn through trials. Each trial is successful if the child ...
2
votes
0answers
60 views

Help with propositional logic

Hi all this is for a homework where we just started learning logic and I am not very familiar with propositional logic. So we have two problems: To show a proof of the Sherlock Holmes syllogism ...
1
vote
0answers
18 views

Propositonal equivalence and compound proposition

Without using truth tables, show that the statements ‘If you did all problems in the book, attended all lectures and completed all assignments, then you will get an A in Discrete Math’ and ...
1
vote
0answers
67 views

Propisitional logic exam questions and answers

I'm going over exam questions, since my exam is hours away. I'd be extremely grateful if you could check out my answers and evaluate them. Hopefully you guys can see the truth table. Also, i have ...
1
vote
0answers
82 views

Propositional logic truth tables

For the exam that I am taking, propositional always comes up with identical questions. These include writing a sentences in propositional logic, which I can do. But also drawing a truth table for ...
1
vote
0answers
29 views

Finding DNF for the given problem (Logic)

I'm struggling to find DNF for the given problem: Whats bugging me, is the last line - I'm seemingly unable to get rid of disjunctions in the first 2nd level parenthesis. Any ideas on what am i ...
1
vote
0answers
72 views

Propositional logic question for designing new proof system

Try to solve question from Logic in Computer Science 2nd by Huth & Ryan Natural deduction is not the only possible formal framework for proofs in propositional logic. As an abbreviation, we ...
1
vote
0answers
131 views

Relationship between Propositional and First Order Logic

The language of Propositional Calculus comprises of the logical connectives and sentential symbols $A,B,C$ etc. The sentential letters can have arbitrary semantics and truth values. Two wff $\phi$ ...
1
vote
0answers
69 views

Maximally Consistent Set (Proof by Contradiction)

Yesterday, I asked about feedback for a proof of the following theorem For all $\phi$, $\phi \in \Gamma^{*}$ if and only if $\Gamma^{*} \vdash \phi$. My main concern was the first part $(\to)$, which ...
1
vote
0answers
70 views

Equivalence of two very specific propositional calculi

Let $H$ and $L$ be two propositional calculi. $H$ has as inference rule modus ponens only, and three axiom schemes: P1: $A\rightarrow . B\rightarrow A$ P2: $(A\rightarrow . B\rightarrow ...
1
vote
0answers
208 views

Inverse function in multi-valued logic through the Webb function

Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function. Then ...
0
votes
0answers
67 views

alternative Compactness theorem proof

I'm attempting a problem which requires me to prove the compactness theorem for propositional logic ![enter image description here][1]in a slightly different way to normal. I'm struggling to ...
0
votes
0answers
48 views

Translate n xor expressions to CNF?

I have n xor expressions: a xor b xor c xor d... I want to translate to cnf: The answer of cnf can be found here: http://www.wolframalpha.com/input/?i=a++XOR+b++XOR+c+XOR+d+ I want to write a ...
0
votes
0answers
39 views

Generalized distributive law

Let $p,q,r,C_{ij}$ be formulae in propositional logic, or even simply symbols, i'm only interested in notations. Distributive law says: $$p\vee (q\wedge r)=(p\vee q)\wedge (p\vee r)$$ I want to ...
0
votes
0answers
21 views

Weighted partial MaxSAT (and MinSAT) with real-valued weights?

Consider the following optimization problem ($\min$-version also of interest): $$ \max_{β\in\{0,1\}^m}\{c'φ(β): ψ(β)=1\} = \max_{\phi\in\{0,1\}^n}\{c'\phi: β\in\{0,1\}^m, \phi=φ(β), ψ(β)=1\},$$ ...
0
votes
0answers
66 views

How to write Propositional logic equation

Given $n-1$ teams and $m-1$ days, provide a propositional logic equation to illustrate the following: each team can only play 1 home game per day. All possible permutations must be played. I'm not ...
0
votes
0answers
21 views

If reduct of a formula is Tautology, Then there exists no stable models?

The Definition of a Stable model says that if I is a Stable model of F, this should be the only Interpretation that satisfies the Reduct of the Formula F. But for any formula F', If the reduct of F' ...
0
votes
0answers
23 views

How Can Substitution on Variable Functors Get Represented in a Sequent Calculus?

Here I found a remark that any "Hilbert", perhaps better Frege calculus can get represented by a sequent calculus. Let $\delta$ denote a variable functor of one argument. If we assign 0 to the ...